671. Second Minimum Node In a Binary Tree
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 0
Acceptance rate: 42.8%
Problem Breakdown
The problem requires finding the second minimum value in a special binary tree where each node has either two or zero children. The root’s value is always the smaller of its two children’s values. We need to output the second smallest unique value in the entire tree, or -1 if no such value exists.
Inputs:
- A non-empty binary tree with nodes having non-negative integer values.
- Each node has either two or zero children.
- The root’s value is the minimum of its two children’s values.
Outputs:
- An integer representing the second smallest unique value in the tree, or -1 if it doesn’t exist.
Implicit Constraints/Edge Cases:
- If all nodes have the same value, the output should be -1.
- The tree can have up to 25 nodes.
- Node values are within the range [1, 2^31 - 1].
Intuition
A brute-force approach would involve traversing the entire tree to collect all unique node values and then sorting them to find the second smallest. However, this approach is inefficient in terms of both time (O(n log n) due to sorting) and space (O(n) for storing unique values).
The key insight is that since each parent node’s value is the minimum of its children’s values, we can leverage this property to avoid unnecessary traversals. Specifically:
- If a child node has a different value from its parent, it must be a candidate for the second minimum.
- We can perform a depth-first search (DFS) starting from the root and keep track of the smallest and second smallest unique values encountered.
Approach
- Initialize two variables,
first_minandsecond_min, to store the smallest and second smallest unique values. Setfirst_minto the root’s value andsecond_minto infinity. - Perform a DFS traversal of the tree:
- If a node’s value is greater than
first_minand less thansecond_min, updatesecond_min. - Recursively traverse the left and right children if they exist.
- If a node’s value is greater than
- After the traversal, check if
second_minwas updated from its initial value (infinity). If it was, returnsecond_min; otherwise, return -1.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
- Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack used for DFS traversal. In the worst case, h can be n (for a skewed tree).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findSecondMinimumValue(root: TreeNode) -> int:
first_min = root.val
second_min = float('inf')
def dfs(node):
nonlocal second_min
if node is None:
return
if first_min < node.val < second_min:
second_min = node.val
dfs(node.left)
dfs(node.right)
dfs(root)
return second_min if second_min != float('inf') else -1
Edge Cases Handled
- All nodes have the same value: The function will correctly return -1 since
second_minremains infinity. - Tree with a single node: The function will correctly return -1 as there is no second minimum value.
- Skewed tree (completely unbalanced): The DFS traversal handles this by only visiting necessary nodes, maintaining O(n) time complexity.