Second Minimum Node In a Binary Tree

Second Minimum Node In a Binary Tree

What is this problem about?

The Second Minimum Node In a Binary Tree interview question gives you a special binary tree where every node satisfies: the node's value is the minimum of its subtree, and each node has exactly 0 or 2 children. The root holds the global minimum. Given such a tree, find the second minimum value in the entire tree. If no second minimum exists, return -1.

Why is this asked in interviews?

Meta and LinkedIn ask this tree problem because it requires reasoning about structural invariants — not just doing a generic traversal. Since every node's value is the minimum of its subtree, the second minimum must be found in subtrees that differ from the root's value. It tests whether candidates can prune recursive exploration intelligently using problem-specific constraints rather than brute-force DFS.

Algorithmic pattern used

The pattern is pruning DFS on a special tree. Perform DFS from the root. At each node, if the node's value is greater than the root value, this node itself is a candidate for the second minimum (return it). If the node's value equals the root value, the second minimum might be deeper in either subtree — recurse into both children. When recursing, take the minimum of valid (non -1) results from left and right subtrees. Base case: if the node is null, return -1.

Example explanation

Tree:

    2
   / \
  2   5
 / \
2   7

Root value = 2 (global minimum).

DFS:

• Root(2) == 2 → recurse left and right.
• Left(2) == 2 → recurse left(2) and right(7).
  • Left(2): leaf, equals root → return -1.
  • Right(7): 7 > 2 → candidate, return 7.
  • Take min(−1, 7) = 7.
• Right(5): 5 > 2 → candidate, return 5.
• Take min(7, 5) = 5.

Second minimum: 5.

Common mistakes candidates make

• Running a full DFS to collect all values then finding the second minimum — this ignores the structural property and is unnecessarily O(n).
• Not handling null children (the tree has 0 or 2 children, so both exist together, but null checks are still needed at leaves).
• Returning the second smallest occurrence rather than the second smallest distinct value.
• Not pruning when a node's value exceeds the root value — once a subtree root exceeds the global minimum, going deeper can only yield larger values.

Interview preparation tip

For the Second Minimum Node In a Binary Tree coding problem, the DFS binary tree interview pattern with pruning is the approach. The pruning condition is key: once you find a value greater than root, don't recurse further into that subtree. Meta interviewers appreciate when you explain why the structural property guarantees this pruning is safe. Practice this pattern — it generalizes to other problems where tree structure provides early termination opportunities.