Second Minimum Node In a Binary Tree

Easy
1878.

Second Minimum Node In a Binary Tree

Second Minimum Node In a Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Microsoft and LinkedIn interviews.

You are given the root of a non-empty special binary tree of positive values: every node has either zero or two children, and a node with two children holds the smaller of its two children's values — node.val == min(node.left.val, node.right.val).

Return the second smallest distinct value in the whole tree, or -1 if there is none (all values are equal).

Example 1

Input
root = [2,2,5,null,null,5,7]
Output
5
Explanation
The smallest value is 2 and the next distinct value is 5.

Example 2

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

Example 3

Input
root = [5,5,2147483647]
Output
2147483647
Explanation
Values may reach 2^31 - 1, so do not use that number as an 'unset' marker.

Constraints

  • The number of nodes in the tree is in the range [1, 25]
  • 1 <= Node.val <= 2^31 - 1
  • Every node has 0 or 2 children, and root.val == min(root.left.val, root.right.val) at every node with children
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findSecondMinimumValue = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Second Minimum Node In a Binary Tree — Problem & Solution

Second Minimum Node In a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Second Minimum Node In a Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Microsoft and LinkedIn interviews.

Problem statement

You are given the root of a non-empty special binary tree of positive values: every node has either zero or two children, and a node with two children holds the smaller of its two children's values — node.val == min(node.left.val, node.right.val).

Return the second smallest distinct value in the whole tree, or -1 if there is none (all values are equal).

Example 1

Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2 and the next distinct value is 5.

Example 2

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

Example 3

Input: root = [5,5,2147483647]
Output: 2147483647
Explanation: Values may reach 2^31 - 1, so do not use that number as an 'unset' marker.

Constraints

  • The number of nodes in the tree is in the range [1, 25]
  • 1 <= Node.val <= 2^31 - 1
  • Every node has 0 or 2 children, and root.val == min(root.left.val, root.right.val) at every node with children

Hints for Second Minimum Node In a Binary Tree

  1. Hint 1

    The rule node.val == min(children) forces the root to hold the smallest value of the whole tree.

  2. Hint 2

    So the answer is the smallest value strictly greater than root.val.

  3. Hint 3

    Once a node's value exceeds root.val, everything below it is at least that large — it is a candidate, and its subtree need not be explored further.

How to solve Second Minimum Node In a Binary Tree

Because every parent holds the minimum of its children, the root holds the global minimum, and every subtree's root is the minimum of that subtree. The answer is the smallest value above root.val, and a search can stop descending at the first node above it on each path.

Approach

  1. Let m = root.val.
  2. DFS from the root. At a node with value greater than m, return its value as a candidate (its descendants are no smaller).
  3. At a node equal to m, return the smaller of its children's candidates, ignoring children that found none.
  4. If no candidate exists anywhere, return -1.

Why it works

Every node's value is the minimum of its subtree, so if a node exceeds m its whole subtree is at least its value and contributes nothing smaller. Only nodes equal to m can hide a smaller second value below them, and those are exactly the ones the search descends through.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth

Pitfalls

  • Values go up to 2^31 - 1; use a 64-bit sentinel or an explicit 'not found', not INT_MAX, for 'no candidate'.
  • The second minimum must be distinct: duplicates of the minimum do not count.
  • Searching only the root's two children is not enough — the second value may sit deeper under a child equal to the root.

Reference solution

Python

from typing import Optional

def findSecondMinimumValue(root: Optional[TreeNode]) -> int:
    m = root.val

    def search(node):
        # The smallest value above m in this subtree, or -1.
        if node is None:
            return -1
        if node.val > m:
            return node.val
        a = search(node.left)
        b = search(node.right)
        if a == -1:
            return b
        if b == -1:
            return a
        return min(a, b)

    return search(root)

Java

public static int findSecondMinimumValue(TreeNode root) {
    return (int) secondSearch(root, root.val);
}

static long secondSearch(TreeNode node, int m) {
    if (node == null) return -1;
    if (node.val > m) return node.val;
    long a = secondSearch(node.left, m);
    long b = secondSearch(node.right, m);
    if (a == -1) return b;
    if (b == -1) return a;
    return Math.min(a, b);
}

C++

long long secondSearch(TreeNode* node, int m) {
    if (!node) return -1;
    if (node->val > m) return node->val;
    long long a = secondSearch(node->left, m);
    long long b = secondSearch(node->right, m);
    if (a == -1) return b;
    if (b == -1) return a;
    return min(a, b);
}

int findSecondMinimumValue(TreeNode* root) {
    return (int) secondSearch(root, root->val);
}

JavaScript

var findSecondMinimumValue = function(root) {
    return secondSearch(root, root.val);
};

var secondSearch = function(node, m) {
    if (node === null) return -1;
    if (node.val > m) return node.val;
    var a = secondSearch(node.left, m);
    var b = secondSearch(node.right, m);
    if (a === -1) return b;
    if (b === -1) return a;
    return Math.min(a, b);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals