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-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.
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.
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 isn't any second smallest value.
Constraints:
[1, 25].1 <= Node.val <= 231 - 1root.val == min(root.left.val, root.right.val) for each internal node of the tree.In #671 Second Minimum Node In a Binary Tree, the tree follows a special rule: every node’s value is equal to the min of its children, meaning the root always holds the smallest value in the entire tree. The goal is to find the second smallest value among all nodes.
A common strategy is to perform a Depth-First Search (DFS) starting from the root. Since the root contains the minimum value, we store it and traverse the tree looking for the smallest value greater than the root. When visiting each node, compare its value with the root value. If it is greater, it becomes a candidate for the second minimum. If it is equal to the root value, continue exploring its children.
Because of the tree’s special property, branches with values already larger than the current candidate can often be ignored, improving efficiency. The traversal ensures every relevant node is checked while maintaining a global candidate value. The overall complexity remains linear relative to the number of nodes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (DFS) traversal | O(n) | O(h) recursion stack, where h is tree height |
Inside code
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem guarantees a special tree property where each node equals the minimum of its children. Because of this rule, the root value propagates upward as the smallest value in the entire tree.
Yes, variations of this problem appear in technical interviews, especially those testing tree traversal and reasoning about constraints. Companies often use it to evaluate DFS understanding and problem-specific optimizations.
A binary tree traversal using recursion or a stack works best. DFS is commonly used because it naturally explores all nodes while keeping track of candidate values for the second minimum.
The optimal approach is to use Depth-First Search (DFS). Since the root contains the smallest value, traverse the tree and track the smallest value greater than the root. This allows you to find the second minimum efficiently in a single pass.