Second Minimum Node In a Binary Tree — Solution

Problem

Given a special binary tree where every node has exactly two or zero children, and every node's value equals the minimum value among itself and all its descendants, find the second minimum distinct value across all nodes in the tree. If no such value exists, return -1.

[2,2,5,null,null,5,7]

• Input: root = [2, 2, 5, null, null, 5, 7]
• Output: 5
• Explanation: The distinct values in the tree are 2, 5, and 7 — the second smallest is 5.

A case where -1 is the answer:

[2,2,2]

• Input: root = [2, 2, 2]
• Output: -1
• Explanation: Every node has value 2, so there is no second distinct minimum.

Intuition

Because every node's value is guaranteed to be less than or equal to its children, the root always holds the global minimum. The second minimum must be the smallest value in the tree that is strictly greater than the root. A DFS can find it efficiently: as soon as a node's value exceeds the root's, its entire subtree can be pruned — the tree property guarantees no descendant will be smaller than that node.

Solution — DFS with Pruning

Track the root's value as the known global minimum. For each node visited, if its value exceeds the minimum it is a candidate for second minimum and its subtree can be skipped; if it equals the minimum, recurse into its children where the second minimum may be hiding.

1. Record root.val as min_val and initialize second_min to infinity.
2. Run DFS from the root.
3. At each node: if null, return; if node.val > min_val, update second_min and stop (prune subtree); otherwise recurse into both children.
4. After DFS, return second_min if it was updated, or -1 if it is still infinity.

1from typing import Optional
2
3class Solution:
4    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
5        min_val = root.val
6        second_min = float('inf')
7
8        def dfs(node):
9            nonlocal second_min
10            if node is None:
11                return
12            # Candidate found; all descendants >= node.val, so no need to go deeper
13            if node.val > min_val:
14                second_min = min(second_min, node.val)
15                return
16            # node.val == min_val; second minimum could be further down
17            dfs(node.left)
18            dfs(node.right)
19
20        dfs(root)
21        return second_min if second_min != float('inf') else -1

Time: O(n) — each node is visited at most once before being returned or pruned.

Space: O(h) — the recursion stack reaches at most the height of the tree, which is O(log n) for a balanced tree and O(n) for a skewed one.

Complexity Summary

Common Mistakes

• Returning min(root.left.val, root.right.val) directly — wrong if both children equal the root's value, because the actual second minimum may be several levels deeper.
• Not pruning when node.val > min_val — safe to stop here since the tree property guarantees all descendants are ≥ the current node's value; recursing deeper wastes time.
• Treating values equal to the root as candidates — the second minimum must be strictly greater than root.val; equal values do not count.
• Using int as the sentinel in Java or C++ — initializing second_min to Integer.MAX_VALUE and then casting can cause overflow; use Long.MAX_VALUE / LONG_MAX and cast only at the return.
• Returning 0 or INT_MIN when no second minimum exists — the problem requires -1 specifically when all node values are identical; skipping the infinity check produces a wrong answer.

Related Problems

• maximum-depth-of-binary-tree — same DFS traversal pattern, returning a computed value from leaf to root
• minimum-depth-of-binary-tree — DFS with early termination once a leaf meeting a condition is found
• path-sum — DFS on a binary tree accumulating a running value and checking a condition
• kth-smallest-element-in-a-bst — finding the k-th ordered element in a tree using structural properties
• symmetric-tree — recursive tree comparison that mirrors the "exploit tree structure to prune work" pattern