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.Problem Overview: You are given a special binary tree where every non-leaf node has exactly two children and its value equals the smaller of its two children's values. Because of this rule, the root always contains the smallest value in the entire tree. The task is to find the second smallest value across all nodes. If such a value does not exist, return -1.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
This approach traverses the tree using recursion and tracks the smallest value (which is always the root). During traversal, you look for the smallest value strictly greater than root.val. DFS works well because you can explore each subtree while maintaining the current candidate for the second minimum. When visiting a node, if its value is greater than the root value, it becomes a candidate and you compare it with the best answer found so far. Otherwise, you continue exploring its children. Since every node may need to be visited in the worst case, the time complexity is O(n). The recursion stack uses O(h) space where h is the tree height.
The key insight comes from the tree property: each parent equals the minimum of its children. That means any value greater than root.val automatically qualifies as a candidate for the second minimum. DFS naturally explores deeper branches first and is a clean way to implement this logic in problems involving Depth-First Search on a Binary Tree.
Approach 2: Iterative Breadth-First Search (BFS) (Time: O(n), Space: O(n))
The BFS approach uses a queue to traverse the tree level by level. Start by storing the root's value as the global minimum. While processing nodes from the queue, check if the node value is greater than the root value. If it is, update the second minimum candidate. If the node value equals the root value, its children might still contain larger values, so push them into the queue for further exploration. This ensures that all potential candidates are examined.
BFS processes nodes iteratively and avoids recursion. The time complexity remains O(n) because each node is processed once. The queue can store up to a full level of the tree, resulting in O(n) auxiliary space in the worst case. BFS is commonly used when working with general Tree traversals and is helpful when recursion depth could become large.
Recommended for interviews: The recursive DFS solution is usually preferred. It directly leverages the special property of the tree and keeps the code compact. Interviewers typically expect you to recognize that the root already holds the minimum value and then search for the smallest value greater than it using a full traversal. BFS is equally valid but slightly more verbose.
This approach utilizes the recursive Depth-First Search (DFS) to traverse through the binary tree. Since each parent node value is equal to the minimum of its two children nodes, we need to traverse the tree to collect candidate values for the second minimum. This is done by keeping track of unique values found during traversal.
The C code implements a recursive DFS to explore each node, focusing on nodes with values different from the root (which holds the minimum value). It checks if a value smaller than the current second minimum is found, hence keeps updating the potential second minimum.
Time Complexity: O(n), where n is the number of nodes in the tree. You visit each node once.
Space Complexity: O(h), where h is the height of the tree due to call stack usage in recursion.
This approach utilizes an iterative Breadth-First Search (BFS) using a queue to process nodes level by level. It maintains a minimum and a candidate for the second minimum. By using a level-order traversal, it systematically updates the second minimum whenever a node with a greater value than the minimum is discovered.
This C implementation uses a queue for BFS traversal. It starts with the root's value as the minimum and traverses level by level. Each node value is compared against the current minimum and potential second minimum, updating if conditions are met.
Time Complexity: O(n), processes each node once.
Space Complexity: O(w), where w is the maximum width of the tree (auxiliary space used by the queue).
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) Approach | Time Complexity: O(n), where n is the number of nodes in the tree. You visit each node once. |
| Iterative Breadth-First Search (BFS) Approach | Time Complexity: O(n), processes each node once. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Preferred interview solution; clean recursion that leverages tree properties |
| Iterative Breadth-First Search (BFS) | O(n) | O(n) | Useful when avoiding recursion or when performing level-order traversal |
花花酱 LeetCode 671. Second Minimum Node In a Binary Tree - 刷题找工作 EP34 • Hua Hua • 6,651 views views
Watch 9 more video solutions →Practice Second Minimum Node In a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor