Second Minimum Node In a Binary Tree — Problem & Solution
Second Minimum Node In a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Second Minimum Node In a Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Microsoft and LinkedIn interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Microsoft, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a non-empty special binary tree of positive values: every node has either zero or two children, and a node with two children holds the smaller of its two children's values — node.val == min(node.left.val, node.right.val).
Return the second smallest distinct value in the whole tree, or -1 if there is none (all values are equal).
Example 1
Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2 and the next distinct value is 5.
Example 2
Input: root = [2,2,2]
Output: -1
Explanation: Every value is 2, so there is no second distinct value.
Example 3
Input: root = [5,5,2147483647]
Output: 2147483647
Explanation: Values may reach 2^31 - 1, so do not use that number as an 'unset' marker.
Constraints
The number of nodes in the tree is in the range [1, 25]1 <= Node.val <= 2^31 - 1Every node has 0 or 2 children, androot.val == min(root.left.val, root.right.val)at every node with children
Hints for Second Minimum Node In a Binary Tree
Hint 1
The rule
node.val == min(children)forces the root to hold the smallest value of the whole tree.Hint 2
So the answer is the smallest value strictly greater than
root.val.Hint 3
Once a node's value exceeds
root.val, everything below it is at least that large — it is a candidate, and its subtree need not be explored further.
How to solve Second Minimum Node In a Binary Tree
Because every parent holds the minimum of its children, the root holds the global minimum, and every subtree's root is the minimum of that subtree. The answer is the smallest value above root.val, and a search can stop descending at the first node above it on each path.
Approach
- Let
m = root.val. - DFS from the root. At a node with value greater than
m, return its value as a candidate (its descendants are no smaller). - At a node equal to
m, return the smaller of its children's candidates, ignoring children that found none. - If no candidate exists anywhere, return -1.
Why it works
Every node's value is the minimum of its subtree, so if a node exceeds m its whole subtree is at least its value and contributes nothing smaller. Only nodes equal to m can hide a smaller second value below them, and those are exactly the ones the search descends through.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth
Pitfalls
- Values go up to
2^31 - 1; use a 64-bit sentinel or an explicit 'not found', notINT_MAX, for 'no candidate'. - The second minimum must be distinct: duplicates of the minimum do not count.
- Searching only the root's two children is not enough — the second value may sit deeper under a child equal to the root.
Reference solution
Python
from typing import Optional
def findSecondMinimumValue(root: Optional[TreeNode]) -> int:
m = root.val
def search(node):
# The smallest value above m in this subtree, or -1.
if node is None:
return -1
if node.val > m:
return node.val
a = search(node.left)
b = search(node.right)
if a == -1:
return b
if b == -1:
return a
return min(a, b)
return search(root)Java
public static int findSecondMinimumValue(TreeNode root) {
return (int) secondSearch(root, root.val);
}
static long secondSearch(TreeNode node, int m) {
if (node == null) return -1;
if (node.val > m) return node.val;
long a = secondSearch(node.left, m);
long b = secondSearch(node.right, m);
if (a == -1) return b;
if (b == -1) return a;
return Math.min(a, b);
}C++
long long secondSearch(TreeNode* node, int m) {
if (!node) return -1;
if (node->val > m) return node->val;
long long a = secondSearch(node->left, m);
long long b = secondSearch(node->right, m);
if (a == -1) return b;
if (b == -1) return a;
return min(a, b);
}
int findSecondMinimumValue(TreeNode* root) {
return (int) secondSearch(root, root->val);
}JavaScript
var findSecondMinimumValue = function(root) {
return secondSearch(root, root.val);
};
var secondSearch = function(node, m) {
if (node === null) return -1;
if (node.val > m) return node.val;
var a = secondSearch(node.left, m);
var b = secondSearch(node.right, m);
if (a === -1) return b;
if (b === -1) return a;
return Math.min(a, b);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals