Second Minimum Node In a Binary Tree — DFS with Pruning in O(n)

Problem Statement#

Given a non-empty special binary tree where each node has either two children or zero children, and root.val == min(root.left.val, root.right.val), return the second minimum value across all nodes. If no second minimum exists, return -1.

Constraints:

• Number of nodes is in [1, 25]
• 1 <= Node.val <= 2^31 - 1
• root.val == min(root.left.val, root.right.val) for every internal node

Input:  root = [2,2,5,null,null,5,7]
Output: 5

Input:  root = [2,2,2]
Output: -1

Why This Problem Matters#

LeetCode 671 "Second Minimum Node In a Binary Tree" is an Amazon and Lyft favorite, especially in early-career and SDE-1 phone screens. It teaches a classic interview tactic: read constraints carefully and exploit them. The constraint root.val == min(left.val, right.val) collapses the search to nodes strictly greater than root.val, and the smallest such value is the answer.

It is also a great example of when a generic solution (collect all values, sort, find second unique) is overkill. The structural property unlocks a tighter algorithm.

The Core Insight#

Because the root is always the minimum, the second minimum must be the smallest value strictly greater than root.val that appears anywhere in the tree. DFS the tree and track the smallest such candidate.

Crucial pruning: if a subtree's root already exceeds our best candidate, no need to descend further — the same property guarantees the entire subtree's values are at least the subtree's root, so they cannot improve the answer. This keeps the algorithm efficient on tall, value-monotone subtrees.

Visual Dry Run#

Tree [2,2,5,null,null,5,7], root.val = 2.

Return 5.

Solution (Optimal)#

class Solution:
    def findSecondMinimumValue(self, root):
        first = root.val
        self.best = float('inf')
 
        def dfs(node):
            if not node:
                return
            if first < node.val < self.best:
                self.best = node.val
                return
            if node.val == first:
                dfs(node.left)
                dfs(node.right)
 
        dfs(root)
        return -1 if self.best == float('inf') else self.best

var findSecondMinimumValue = function(root) {
    const first = root.val;
    let best = Infinity;
 
    const dfs = (node) => {
        if (!node) return;
        if (node.val > first && node.val < best) {
            best = node.val;
            return;
        }
        if (node.val === first) {
            dfs(node.left);
            dfs(node.right);
        }
    };
 
    dfs(root);
    return best === Infinity ? -1 : best;
};

Time: O(n) worst case — visit every node when all values equal root.val. Space: O(h) — recursion stack, where h is tree height.

Common Mistakes#

• Forgetting that the answer must be strictly greater than root.val — equal values do not count.
• Using only INT_MAX as a sentinel without distinguishing "not found" from "answer is INT_MAX".
• Iterating with sort: O(n log n) — works but misses the structural insight.
• Failing to prune subtrees rooted above the current best.
• Using Number.MAX_SAFE_INTEGER carelessly when values can reach 2^31 - 1.

Interview Tips#

• Open with: "Root is the global min. So the answer is the smallest value strictly greater than root.val."
• Mention the pruning rule explicitly — interviewers love to hear "we can stop descending here because…".
• Discuss the alternative O(n log n) sort approach, then explain why your DFS is better.
• Watch for overflow corner cases — use a language-appropriate "infinity" sentinel.

Follow-up Questions#

• K-th minimum: generalize to find the k-th distinct value. Hint: heap of size k or sorted set.
• Drop the structural property: find second minimum in any binary tree. Hint: track two best values during a single pass.
• Streaming version: values arrive online. Hint: maintain a fixed-size min-heap.
• Multiple trees: find the second min across a forest. Hint: take the global second min after combining roots.
• Allow ties for second: count nodes equal to second min. Hint: extend DFS with a counter.

Key Takeaways#

• LeetCode 671 leans entirely on the structural rule root.val == min(left, right).
• The answer is the smallest value strictly greater than root.val.
• Prune subtrees whose root is not less than the current best candidate.
• Return -1 when no value strictly greater than root.val exists.
• O(n) time worst-case, O(h) space — better than the O(n log n) sort approach.
• Common at Amazon and Lyft for entry-level tree screens.
• Train yourself to spot constraints that collapse a problem to a special case.