LeetCode 671: Second Minimum Node In a Binary Tree

Problem Restatement

We are given a non-empty special binary tree.

The tree has these rules:

If no second minimum value exists, return -1.

Because each parent stores the smaller value of its children, the root always contains the minimum value in the entire tree. The task is to find the smallest value strictly greater than the root value.

Input and Output

Example function shape:

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

Examples

Consider this tree:

    2
   / \
  2   5
     / \
    5   7

The values in the tree are:

2, 2, 5, 5, 7

The minimum value is:

2

The second minimum value is:

5

So the answer is:

5

Now consider:

  2
 / \
2   2

All values are the same.

There is no value strictly greater than 2.

So the answer is:

-1

First Thought: Collect All Values

A direct solution is to traverse the tree, collect all node values into a list, remove duplicates, sort the values, and return the second value.

This works, but it stores more data than needed.

We already know the smallest value:

root.val

So we only need to find the smallest value greater than root.val.

Key Insight

Because of the special tree property, the root value is the global minimum.

Therefore, every node value is either:

1. Equal to root.val
2. Greater than root.val

The answer is the smallest value in the second group.

So we can run DFS and keep one variable:

answer

Whenever we find a node value greater than the root value, it becomes a candidate for the second minimum.

We keep the smallest candidate.

Pruning Observation

There is also a useful pruning rule.

If a node value is already greater than the root value, then this node is a candidate.

Because every descendant of that node must be greater than or equal to that node, no descendant can give a smaller candidate.

So once we see:

node.val > root.val

we can return node.val for that subtree.

This gives a clean recursive solution.

Algorithm

Use a helper function:

dfs(node)

It returns the second minimum candidate inside that subtree, or -1 if none exists.

For each node:

1. If node is None, return -1.
2. If node.val > minimum, return node.val.
3. Recursively search the left subtree.
4. Recursively search the right subtree.
5. If both sides return valid candidates, return the smaller one.
6. If only one side is valid, return that one.
7. If neither side is valid, return -1.

Correctness

The root value is the minimum value of the whole tree because each internal node stores the smaller value of its children.

The DFS helper searches for the smallest value strictly greater than this minimum.

If a node value is greater than the minimum, that node is a valid second-minimum candidate. Its descendants cannot contain a smaller candidate, because the special tree property implies descendants are greater than or equal to their ancestors. Therefore, returning that node value for the subtree is correct.

If a node value equals the minimum, the second minimum may still appear in either child subtree, so the algorithm searches both children.

For each subtree, the helper returns the smallest valid candidate in that subtree, or -1 if none exists. Combining the left and right results by taking the smaller valid candidate gives the smallest valid candidate for the current subtree.

Applying this logic at the root returns the smallest value strictly greater than the global minimum. If no such value exists, the algorithm returns -1.

Complexity

Here, n is the number of nodes and h is the height of the tree.

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        minimum = root.val

        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return -1

            if node.val > minimum:
                return node.val

            left = dfs(node.left)
            right = dfs(node.right)

            if left == -1:
                return right

            if right == -1:
                return left

            return min(left, right)

        return dfs(root)

Code Explanation

The root value is the global minimum:

minimum = root.val

The helper returns the second-minimum candidate inside a subtree:

def dfs(node: Optional[TreeNode]) -> int:

If the node is missing, it gives no candidate:

if node is None:
    return -1

If the node value is greater than the root value, it is a candidate:

if node.val > minimum:
    return node.val

We can return immediately because descendants cannot improve this candidate within that subtree.

If the node value equals the minimum, the answer may be deeper:

left = dfs(node.left)
right = dfs(node.right)

If one side has no candidate, return the other side:

if left == -1:
    return right

if right == -1:
    return left

If both sides have candidates, return the smaller one:

return min(left, right)

Testing

def run_tests():
    s = Solution()

    # Tree:
    #     2
    #    / \
    #   2   5
    #      / \
    #     5   7
    root = TreeNode(2)
    root.left = TreeNode(2)
    root.right = TreeNode(5, TreeNode(5), TreeNode(7))

    assert s.findSecondMinimumValue(root) == 5

    # Tree:
    #   2
    #  / \
    # 2   2
    root = TreeNode(2, TreeNode(2), TreeNode(2))

    assert s.findSecondMinimumValue(root) == -1

    # Single node.
    root = TreeNode(1)

    assert s.findSecondMinimumValue(root) == -1

    # Candidate appears in the left subtree.
    root = TreeNode(1)
    root.left = TreeNode(1, TreeNode(1), TreeNode(3))
    root.right = TreeNode(1, TreeNode(1), TreeNode(5))

    assert s.findSecondMinimumValue(root) == 3

    print("all tests passed")

run_tests()

Test meaning: