671 · Second Minimum Node In a Binary Tree

The tree has a peculiar guarantee: every node has either zero or two children, and each node's value is the minimum of its two children. That single property collapses the problem — the root is the smallest value in the whole tree, so the task is just "find the smallest value strictly greater than the root" — and it also licenses a prune that makes the search stop early.

1 — Why the root is the minimum

If every node is the smaller of its two children, then no descendant can be smaller than its ancestor. Chain that from the root and the root's value is a lower bound for the entire tree. So the answer is the smallest value anywhere that is strictly greater than root.val — or -1 if no such value exists.

The same property gives you the prune. If you reach a node whose value already exceeds the root, every value beneath it is at least its value, so nothing down there can be a better candidate. Record it and turn around.

2 — The search, with pruning

root = [2,2,5,null,null,5,7]. Expected answer: 5.

void dfs(TreeNode nd) {    if (nd == null) return;    if (nd.val > min) {        // candidate — and everything below is >= nd.val        if (second == -1 || nd.val < second) second = nd.val;        return;                     // prune    }    dfs(nd.left); dfs(nd.right);      // nd.val == min, keep going}

The 7 is never visited. That is the prune earning its keep: it costs one comparison and can cut off an arbitrarily large subtree.

3 — When there is no answer

root = [2,2,2]. Every value is identical, so nothing exceeds the root.

void dfs(TreeNode nd) {    if (nd == null) return;    if (nd.val > min) {        // candidate — and everything below is >= nd.val        if (second == -1 || nd.val < second) second = nd.val;        return;                     // prune    }    dfs(nd.left); dfs(nd.right);      // nd.val == min, keep going}

Returning -1 here is easy to forget, and easy to get subtly wrong: if you initialise your answer to Integer.MAX_VALUE and return it unchanged, you report 2147483647 instead of −1. Either initialise to -1 and special-case the first candidate, or use a long sentinel and translate at the end.

4 — Complexity and edge cases

• Time: O(n) worst case — a tree where every value equals the root forces a full traversal, because the prune never fires. In practice it fires early and often.
• Space: O(h) for the recursion.
• A single node has no second value: return -1.
• Values reach 2³¹ − 1, which is exactly why Integer.MAX_VALUE is a dangerous sentinel here — it is a legal node value.
• Do not sort or collect everything. Gathering all values into a set and taking the second smallest is O(n log n) and throws away the structural property the problem was built around; interviewers ask this one specifically to see whether you notice it.

5 — Reference implementation

private int min, second = -1;

public int findSecondMinimumValue(TreeNode root) {
    min = root.val;                        // the root is the tree minimum
    dfs(root);
    return second;
}

private void dfs(TreeNode nd) {
    if (nd == null) return;
    if (nd.val > min) {
        if (second == -1 || nd.val < second) second = nd.val;
        return;                             // prune: subtree values are all >= nd.val
    }
    dfs(nd.left);
    dfs(nd.right);
}