Second Minimum Node In a Binary Tree

Difficulty: Easy | Acceptance: 46.10% | Paid: No Topics: Tree, Depth-First Search, Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

As such, the root of the tree is the minimum value in the whole tree.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

• Examples
• Constraints
• Brute Force Set Traversal
• Depth-First Search (Optimal)
• Breadth-First Search

Examples

Example 1:

Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: root = [2,2,2]
Output: -1
Explanation: The smallest value is 2, but there is not a second smallest value.

Constraints

The number of nodes in the tree is in the range [1, 25].
1 <= Node.val <= 2³¹ - 1
Each node in this tree has exactly two or zero sub-nodes.
All nodes in the tree have distinct values if the tree has more than one node.

Brute Force Set Traversal

Intuition Traverse the entire tree to collect all unique node values into a set. Since the root is the minimum, the second minimum is simply the smallest value in the set that is strictly greater than the root value.

Steps

• Initialize an empty set to store unique values.
• Perform a traversal (DFS or BFS) of the tree, adding every node’s value to the set.
• If the set contains fewer than 2 values, return -1.
• Otherwise, find the smallest value in the set that is greater than the root’s value.

class Solution:
    def findSecondMinimumValue(self, root):
        values = set()
        
        def dfs(node):
            if not node:
                return
            values.add(node.val)
            dfs(node.left)
            dfs(node.right)
            
        dfs(root)
        
        if len(values) < 2:
            return -1
        
        # Remove the minimum (root.val) and find the new minimum
        values.remove(root.val)
        return min(values)

Complexity

• Time: O(N log N) due to sorting the set/array in the worst case (though TreeSet/SortedSet handles insertion in O(log N), overall complexity is dominated by sorting or iteration).
• Space: O(N) to store the set of values.
• Notes: Simple to implement but uses extra space proportional to the number of nodes.

Depth-First Search (Optimal)

Intuition Since the root value is the global minimum, we only need to find the smallest value in the tree that is strictly greater than root.val. We can traverse the tree and keep track of the minimum candidate found so far.

Steps

• Initialize a variable ans to a value larger than the maximum possible node value (e.g., Infinity or Long.MAX_VALUE).
• Traverse the tree using DFS.
• If a node’s value is greater than root.val and less than the current ans, update ans.
• After traversal, if ans remains at the initial large value, return -1. Otherwise, return ans.

class Solution:
    def findSecondMinimumValue(self, root):
        self.ans = float('inf')
        min_val = root.val
        
        def dfs(node):
            if not node:
                return
            if min_val < node.val < self.ans:
                self.ans = node.val
                # Optimization: if we find the immediate successor, we can stop early
                # but for simplicity we continue or could add a check here
            dfs(node.left)
            dfs(node.right)
            
        dfs(root)
        return -1 if self.ans == float('inf') else self.ans

Complexity

• Time: O(N) where N is the number of nodes. We visit each node once.
• Space: O(H) where H is the height of the tree, for the recursion stack.
• Notes: This is the most optimal approach as it avoids storing all values and sorts implicitly during traversal.

Breadth-First Search

Intuition Similar to the optimal DFS approach, we can use a queue to traverse the tree level by level, keeping track of the smallest value found that is greater than the root’s value.

Steps

• Initialize ans to a large value (e.g., Infinity).
• Initialize a queue with the root node.
• While the queue is not empty:
  • Dequeue a node.
  • If the node’s value is greater than root.val and less than ans, update ans.
  • Enqueue the left and right children if they exist.
• Return ans if updated, otherwise -1.

from collections import deque

class Solution:
    def findSecondMinimumValue(self, root):
        min_val = root.val
        ans = float('inf')
        q = deque([root])
        
        while q:
            node = q.popleft()
            if min_val < node.val < ans:
                ans = node.val
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
                
        return -1 if ans == float('inf') else ans

Complexity

• Time: O(N) where N is the number of nodes.
• Space: O(W) where W is the maximum width of the tree (for the queue).
• Notes: Useful if you prefer iterative solutions or want to avoid recursion stack overflow on very deep trees (though constraints are small here).