Second Minimum Node In a Binary Tree

easy tree dfs

Problem

Given a non-empty special binary tree where each non-leaf node has exactly two children and root.val == min(left.val, right.val), return the second minimum value in the tree, or -1 if it does not exist.

Inputroot = [2,2,5,null,null,5,7]

Output5

The smallest value is 2 (the root). The smallest value strictly greater than 2 is 5.

tree (level-order, "null" for empty)

def find_second_minimum(root):
    first = root.val
    ans = [-1]
    def dfs(n):
        if not n:
            return
        if ans[0] != -1 and n.val >= ans[0]:
            return
        if n.val > first:
            ans[0] = n.val
        dfs(n.left); dfs(n.right)
    dfs(root)
    return ans[0]

function findSecondMinimumValue(root) {
  const first = root.val;
  let ans = -1;
  (function dfs(n) {
    if (!n) return;
    if (ans !== -1 && n.val >= ans) return;
    if (n.val > first) ans = n.val;
    dfs(n.left); dfs(n.right);
  })(root);
  return ans;
}

class Solution {
    int first; long ans = -1;
    public int findSecondMinimumValue(TreeNode root) {
        first = root.val; dfs(root);
        return (int) ans;
    }
    void dfs(TreeNode n) {
        if (n == null) return;
        if (ans != -1 && n.val >= ans) return;
        if (n.val > first) ans = n.val;
        dfs(n.left); dfs(n.right);
    }
}

int findSecondMinimumValue(TreeNode* root) {
    int first = root->val; long ans = -1;
    function<void(TreeNode*)> dfs = [&](TreeNode* n) {
        if (!n) return;
        if (ans != -1 && n->val >= ans) return;
        if (n->val > first) ans = n->val;
        dfs(n->left); dfs(n->right);
    };
    dfs(root); return (int) ans;
}

Explanation

This tree has a special rule: every parent equals the minimum of its two children, so the overall smallest value sits at the root. That means the answer we want — the second-smallest distinct value — is simply the smallest value strictly greater than the root.

We record first = root.val and start ans = -1 (meaning "none found yet"). Then we DFS the tree looking for the smallest value that beats first.

Two prunes keep it fast. If we already have an ans and the current node's value is >= ans, nothing below it can be smaller than ans (the min-rule guarantees children are at least as large), so we stop descending. When a node's value is > first, it's a candidate, so we set ans = n.val.

Example: [2, 2, 5, null, null, 5, 7]. The root is 2, so first = 2. The left child 2 is not greater than first, but its subtree gets explored; the node 5 beats 2 and sets ans = 5. After that, anything >= 5 (like 7) is pruned, so the answer stays 5.

If no value ever exceeds the root, ans remains -1, which correctly signals that no second minimum exists.

Time: O(n) Space: O(h)