Second Minimum Node In a Binary Tree
EasyPrompt
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:
- The number of nodes in the tree is in the range
[1, 25]. 1 <= Node.val <= 231 - 1root.val == min(root.left.val, root.right.val)for each internal node of the tree.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves traversing the entire binary tree to collect all unique node values. These unique values are then sorted to easily identify the second smallest value.
Algorithm
- Initialize a
HashSetto store unique node values. - Perform a depth-first search (DFS) or breadth-first search (BFS) to traverse the tree.
- For each node visited, add its value to the
HashSet. This automatically handles duplicates. - After the traversal, convert the
HashSetinto aList. - Sort the list in ascending order.
- If the list contains fewer than two elements, it means there is no second minimum value, so return -1.
- Otherwise, the second element in the sorted list (at index 1) is the second minimum value.
Walkthrough
This method treats the problem as a generic task of finding the second smallest element in a collection of numbers, ignoring the special structure of the tree. We first gather all unique values from the tree into a set to handle duplicates, then convert the set to a list and sort it. The second element of the sorted list is our answer.
import java.util.*; /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int findSecondMinimumValue(TreeNode root) { Set<Integer> uniqueValues = new HashSet<>(); dfs(root, uniqueValues); if (uniqueValues.size() < 2) { return -1; } List<Integer> sortedValues = new ArrayList<>(uniqueValues); Collections.sort(sortedValues); return sortedValues.get(1); } private void dfs(TreeNode node, Set<Integer> uniqueValues) { if (node == null) { return; } uniqueValues.add(node.val); dfs(node.left, uniqueValues); dfs(node.right, uniqueValues); }}Complexity
Time
O(N log N), where N is the number of nodes. The tree traversal takes O(N) time. Storing U unique values and then sorting them takes O(U log U), where U ≤ N. The sorting step dominates the complexity.
Space
O(N) in the worst case, to store all node values in the `HashSet` if they are all unique.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Guaranteed to be correct for any tree.
Cons
Suboptimal as it requires sorting, which is generally not necessary.
Fails to use the special property of the tree (
root.val = min(root.left.val, root.right.val)) to improve efficiency.
A more efficient approach is to traverse the tree just once. During the traversal, we can keep track of the two smallest distinct values encountered so far.
Algorithm
- From the problem description, we know
root.valis the absolute minimum value in the tree. Let's call thismin1. - Initialize a variable,
min2, to store the second minimum value. Initialize it to a value larger than any possible node value, likeLong.MAX_VALUE, to indicate it hasn't been found yet. - Traverse the tree using DFS or BFS.
- For each node, compare its value (
val) withmin1andmin2. - If
min1 < val < min2, we have found a new, smaller candidate for the second minimum. Updatemin2 = val. - After the traversal is complete, if
min2is stillLong.MAX_VALUE, it means no value greater thanmin1was found. Return -1. - Otherwise, cast
min2to anintand return it.
Walkthrough
Instead of collecting all values, we can find the second minimum in a single pass. We know root.val is the first minimum. We traverse the tree and look for any value that is greater than root.val but smaller than the second minimum found so far. This avoids the overhead of storing all values and sorting.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { long min2 = Long.MAX_VALUE; int min1; public int findSecondMinimumValue(TreeNode root) { if (root == null) { return -1; } min1 = root.val; dfs(root); return (min2 == Long.MAX_VALUE) ? -1 : (int) min2; } private void dfs(TreeNode node) { if (node == null) { return; } if (min1 < node.val && node.val < min2) { min2 = node.val; } dfs(node.left); dfs(node.right); }}Complexity
Time
O(N), where N is the number of nodes. We visit every node in the tree exactly once.
Space
O(H), where H is the height of the tree, for the recursion stack in the DFS approach. In the worst case of a skewed tree, this can be O(N).
Trade-offs
Pros
Improves upon the brute-force approach by eliminating the sorting step.
Achieves linear time complexity.
Cons
It always traverses the entire tree, which can be inefficient if the second minimum value is located near the root.
This is the most efficient approach, as it fully leverages the special property of the tree: node.val = min(node.left.val, node.right.val). This property allows us to prune entire subtrees from our search, leading to better average-case performance.
Algorithm
- The minimum value in the tree is
min1 = root.val. We are looking for the smallest value strictly greater thanmin1. - Initialize a variable
anstoLong.MAX_VALUEto track the second minimum found so far. - Use a queue for a breadth-first search (BFS), starting with the
root. - While the queue is not empty, dequeue a node.
- If the node's value is greater than
min1, it's a candidate for the second minimum. We updateans = min(ans, node.val). We do not need to explore this branch further, so we don't add its children to the queue (pruning). - If the node's value is equal to
min1, the second minimum could be in its subtrees. We add its children to the queue to continue the search. - After the traversal, if
ansremainsLong.MAX_VALUE, no second minimum was found. Return -1. Otherwise, return(int) ans.
Walkthrough
We can optimize the traversal by making an observation. The first minimum value is root.val. Any node with a value greater than root.val is a candidate for the second minimum. If we encounter such a node, say node, then node.val is a candidate. All of its descendants will have values greater than or equal to node.val, so we don't need to explore that subtree any further to find a smaller second minimum. We only need to continue searching down paths where nodes have a value equal to root.val.
import java.util.LinkedList;import java.util.Queue; /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int findSecondMinimumValue(TreeNode root) { if (root == null) { return -1; } long ans = Long.MAX_VALUE; int min1 = root.val; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode current = queue.poll(); if (current.val > min1) { ans = Math.min(ans, current.val); // Pruning: No need to explore children } else if (current.val == min1) { if (current.left != null) { queue.offer(current.left); queue.offer(current.right); } } } return ans == Long.MAX_VALUE ? -1 : (int) ans; }}Complexity
Time
O(N), where N is the number of nodes. In the worst case (e.g., a tree where all nodes have the same value), we must visit every node. However, for many trees, the pruning significantly reduces the number of visited nodes.
Space
O(W), where W is the maximum width of the tree, for the BFS queue. In the worst case of a complete binary tree, this is O(N).
Trade-offs
Pros
The most efficient approach on average due to intelligent search space pruning.
Effectively utilizes the unique structure of the input tree.
Cons
The worst-case time and space complexity are asymptotically the same as the non-optimized single-pass traversal.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans = - 1 ; public int findSecondMinimumValue ( TreeNode root ) { dfs ( root , root . val ); return ans ; } private void dfs ( TreeNode root , int val ) { if ( root != null ) { dfs ( root . left , val ); dfs ( root . right , val ); if ( root . val > val ) { ans = ans == - 1 ? root . val : Math . min ( ans , root . val ); } } } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var findSecondMinimumValue = function (root) { let ans = -1; const v = root.val; function dfs(root) { if (!root) { return; } dfs(root.left); dfs(root.right); if (root.val > v) { if (ans == -1 || ans > root.val) { ans = root.val; } } } dfs(root); return ans; };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int ans = - 1 ; int findSecondMinimumValue ( TreeNode * root ) { dfs ( root , root -> val ); return ans ; } void dfs ( TreeNode * root , int val ) { if ( ! root ) return ; dfs ( root -> left , val ); dfs ( root -> right , val ); if ( root -> val > val ) ans = ans == - 1 ? root -> val : min ( ans , root -> val ); } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def findSecondMinimumValue ( self , root : Optional [ TreeNode ]) -> int : def dfs ( root ): if root : dfs ( root . left ) dfs ( root . right ) nonlocal ans , v if root . val > v : ans = root . val if ans == - 1 else min ( ans , root . val ) ans , v = - 1 , root . val dfs ( root ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.