Second Minimum Node in a Binary Tree: DFS with Pruning

You are given a special binary tree where every node has either zero or two children, and each node's value equals the minimum of its two children's values. Return the second minimum value in the entire tree, or -1 if no such value exists.

This is LeetCode 671: Second Minimum Node in a Binary Tree. The special tree property guarantees that root.val is the global minimum. Your job is to find the smallest value that is strictly greater than root.val.

Why this problem matters

The tree property here is the key to everything. Because every parent equals the minimum of its two children, the root is always the smallest value in the tree. You do not need to search for the minimum. You already have it.

That turns the problem into a targeted search: walk the tree looking for the smallest value that differs from the root. The tree structure lets you prune aggressively. If you reach a node whose value is already greater than the root, there is no point going deeper. Its descendants can only have values greater than or equal to it (because of the min-property), so they cannot beat the current candidate. You only recurse into children that match the root value, because those subtrees might still contain a smaller second minimum hidden deeper down.

The approach

Since root.val is the minimum, you need to find the smallest value strictly greater than root.val. DFS with pruning works perfectly:

1. Start DFS from the root. Track root.val as min_val.
2. If the current node's value is greater than min_val, it is a candidate for the answer. Update the result if this value is smaller than the current best. Do not recurse deeper from this node.
3. If the current node's value equals min_val, recurse into both children. The second minimum might be hiding in either subtree.
4. After the full traversal, return the result. If no candidate was ever found, return -1.

Brute force solution

The simplest approach: collect every value in the tree, sort them, and find the second unique value.

def find_second_minimum_value(root):
    values = set()

    def dfs(node):
        if not node:
            return
        values.add(node.val)
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    if len(values) < 2:
        return -1
    sorted_vals = sorted(values)
    return sorted_vals[1]

This works but it visits every node and sorts the result. You can do better.

Optimal solution

def find_second_minimum_value(root):
    res = -1
    min_val = root.val

    def dfs(node):
        nonlocal res
        if not node:
            return
        if node.val > min_val:
            if res == -1 or node.val < res:
                res = node.val
            return
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return res

Let's break down what happens at each node:

• if not node: return is the base case. Null children end the recursion.
• if node.val > min_val means this node differs from the root. It is a candidate. You update res if this is the first candidate (res == -1) or if it is smaller than the current best. Then you return immediately because going deeper cannot produce a smaller candidate.
• If node.val equals min_val, the node matches the root. The second minimum is not here, but it might be in a descendant. Recurse into both children.

Visual walkthrough

Let's trace the DFS on the tree [2, 2, 5, 2, 3]. Watch how the algorithm prunes branches and tracks the candidate.

The algorithm visits the root (2), goes left to node 2 (same as root, recurse), checks left-left node 2 (same, but it is a leaf, stop), checks left-right node 3 (different from root, candidate = 3, prune), then checks right node 5 (different from root, but 5 > 3, so candidate stays 3). The answer is 3.

Complexity analysis

Time for DFS with pruning is O(n) in the worst case. If every node in the tree has the same value except one leaf, you visit every node before finding the single candidate. In practice, pruning often cuts off large subtrees early.

Space is O(h) where h is the height of the tree. That is the recursion stack depth. For a balanced tree, h = log n. For a skewed tree, h = n.

Edge cases to watch for

• All nodes have the same value: there is no second minimum. The DFS never finds a candidate, and res stays -1. Return -1.
• Root with two leaves: the second minimum is simply the larger of the two leaf values (if they differ). If both leaves equal the root, return -1.
• Left-skewed or right-skewed tree: the algorithm still works. It follows the chain of nodes matching root.val and picks up the first differing value it finds.
• Very large tree with only one unique non-root value: the DFS prunes every subtree rooted at a non-root-value node after visiting just the root of that subtree.

The building blocks

This problem is built on two fundamental building blocks:

1. DFS with pruning. You walk the tree depth-first but skip entire subtrees when you know they cannot improve the answer. The pruning condition here is simple: if a node's value already exceeds min_val, its descendants can only have values that are the same or larger (by the tree property), so there is no reason to explore them. This same DFS-with-pruning pattern appears in problems like Validate BST (prune when a node violates the range) and any tree search where subtree properties let you skip work.

2. Tracking a running minimum candidate. As you traverse, you maintain a single variable (res) that holds the best answer so far. Every time you encounter a valid candidate, you compare it against the current best and update if it is smaller. This running-minimum pattern is one of the most common building blocks in algorithm problems.

From understanding to recall

You just traced through a DFS that uses the special tree property to prune branches and track the second minimum with a single variable. The logic is compact: check if the node differs from root, update the candidate, and stop. If it matches, keep going.

But will you remember the pruning condition in an interview? Will you remember to return -1 when no candidate exists, or will you accidentally return 0? Will you remember that you only recurse when the node equals min_val, not when it is less than res?

Understanding is not recall. You understood the solution. Recall means you can write it cold, under pressure, without mixing up the pruning logic or forgetting the nonlocal declaration.

Spaced repetition builds recall. You practice writing the solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the DFS, the pruning check, and the candidate update from scratch. After a few repetitions, the DFS-with-pruning pattern and the running-minimum pattern are automatic.

These building blocks are part of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Minimum Depth of Binary Tree - Another tree problem where the traversal strategy matters. BFS finds the nearest leaf efficiently, just as DFS with pruning finds the second minimum here.
• Balanced Binary Tree - Uses bottom-up DFS with a sentinel value, similar to how this problem uses -1 as the initial sentinel for the result.
• Binary Tree Right Side View - A tree traversal problem where you selectively track certain nodes during the walk, similar to how this problem selectively tracks candidates.