Second Minimum Node In a Binary Tree
Second Minimum Node In a Binary Tree is a easy trees & bst problem solved with the recursion pattern.
The best approach, optimal (dfs with pruning), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (collect distinct values) up.
Problem
You are given the root of a special binary tree of positive integers. Every node has either no children or exactly two, and a node with two children always holds the smaller of its children’s values: node.val == min(node.left.val, node.right.val).
Return the second smallest distinct value found anywhere in the tree. If all values are the same, return -1.
Examples
Example 1
- Input
root = [3,3,5,null,null,5,8]- Output
5- Why
- The distinct values are 3, 5 and 8. The smallest is 3, so the second smallest is 5.
Example 2
- Input
root = [4,4,4]- Output
-1- Why
- Every node holds 4, so there is no second distinct value.
Example 3
- Input
root = [1,1,2,1,6,2,2]- Output
2- Why
- The distinct values are 1, 2 and 6. The 6 is deeper on the left, but 2 is smaller.
Constraints
- The tree has between
1and25nodes. 1 <= Node.val <= 2^31 - 1- Every node has either zero or two children, and a node with children holds the smaller of its two children's values.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (collect distinct values) | O(n log n) | O(n) |
| Optimal (DFS with pruning) | O(n) | O(h) |
1Brute force (collect distinct values)
O(n log n)n insertions into a sorted set.O(n)The set may hold every value, plus the recursion stack.Visit every node, put the values into a sorted set, and return the second element if there is one.
- Traverse the tree and insert every value into a sorted set.
- If the set has fewer than two values, return -1.
- Otherwise return the second smallest value.
class Solution {
public int findSecondMinimumValue(TreeNode root) {
TreeSet<Integer> seen = new TreeSet<>();
collect(root, seen);
if (seen.size() < 2) return -1;
seen.pollFirst();
return seen.first();
}
private void collect(TreeNode node, TreeSet<Integer> seen) {
if (node == null) return;
seen.add(node.val);
collect(node.left, seen);
collect(node.right, seen);
}
}class Solution:
def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
seen = set()
def collect(node):
if node is None:
return
seen.add(node.val)
collect(node.left)
collect(node.right)
collect(root)
if len(seen) < 2:
return -1
return sorted(seen)[1]class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
set<int> seen;
collect(root, seen);
if (seen.size() < 2) return -1;
return *next(seen.begin());
}
private:
void collect(TreeNode* node, set<int>& seen) {
if (node == nullptr) return;
seen.insert(node->val);
collect(node->left, seen);
collect(node->right, seen);
}
};function findSecondMinimumValue(root) {
const seen = new Set();
const collect = (node) => {
if (node === null) return;
seen.add(node.val);
collect(node.left);
collect(node.right);
};
collect(root);
if (seen.size < 2) return -1;
const sorted = [...seen].sort((a, b) => a - b);
return sorted[1];
}2Optimal (DFS with pruning)
O(n)Each node is visited at most once, and whole subtrees are skipped once a larger value is found.O(h)The recursion goes as deep as the tree's height.The root holds the global minimum m. Search for the smallest value greater than m. When a node's value is already greater than m, it is the smallest value in its own subtree (parents are minimums), so return it without going deeper. When it equals m, the answer may lie in either child: search both and take the smaller valid result.
- m = root.val.
- dfs(node): if node is null return -1; if node.val > m return node.val.
- Otherwise a = dfs(node.left), b = dfs(node.right). If either is -1 return the other; else return min(a, b).
- Return dfs(root).
class Solution {
public int findSecondMinimumValue(TreeNode root) {
return dfs(root, root.val);
}
private int dfs(TreeNode node, int m) {
if (node == null) return -1;
if (node.val > m) return node.val;
int a = dfs(node.left, m), b = dfs(node.right, m);
if (a == -1) return b;
if (b == -1) return a;
return Math.min(a, b);
}
}class Solution:
def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
m = root.val
def dfs(node):
if node is None:
return -1
if node.val > m:
return node.val
a, b = dfs(node.left), dfs(node.right)
if a == -1:
return b
if b == -1:
return a
return min(a, b)
return dfs(root)class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
return dfs(root, root->val);
}
private:
int dfs(TreeNode* node, int m) {
if (node == nullptr) return -1;
if (node->val > m) return node->val;
int a = dfs(node->left, m), b = dfs(node->right, m);
if (a == -1) return b;
if (b == -1) return a;
return min(a, b);
}
};function findSecondMinimumValue(root) {
const m = root.val;
const dfs = (node) => {
if (node === null) return -1;
if (node.val > m) return node.val;
const a = dfs(node.left), b = dfs(node.right);
if (a === -1) return b;
if (b === -1) return a;
return Math.min(a, b);
};
return dfs(root);
}Edge cases to test
- A single node (no second value)
- All nodes equal
- The second minimum sits deep below a chain of nodes equal to the root
- The second minimum is
2^31 - 1, so it must not be confused with a sentinel
Hints
Hint 1
Because each parent is the minimum of its children, the root holds the smallest value of the whole tree.
Hint 2
So you are looking for the smallest value that is strictly larger than the root's value.
Hint 3
Once you reach a node whose value is larger than the root's, nothing below it can be smaller, so you can stop descending there.
FAQ
What is the best time complexity for Second Minimum Node In a Binary Tree?
Optimal (DFS with pruning) runs in O(n) time and O(h) extra space. Each node is visited at most once, and whole subtrees are skipped once a larger value is found.
Which pattern does Second Minimum Node In a Binary Tree use?
It is a trees & bst problem that uses the recursion pattern. Other problems with the same pattern: Binary Tree Inorder Traversal (Recursive), Binary Tree Preorder Traversal (Recursive), Binary Tree Postorder Traversal (Recursive).
Is there a brute force solution for Second Minimum Node In a Binary Tree?
Yes. Brute force (collect distinct values) takes O(n log n) time and O(n) space. Visit every node, put the values into a sorted set, and return the second element if there is one.
Which edge cases should I test for Second Minimum Node In a Binary Tree?
A single node (no second value); All nodes equal; The second minimum sits deep below a chain of nodes equal to the root; The second minimum is 2^31 - 1, so it must not be confused with a sentinel.