Domain 1EasyCORE

Second Minimum Node In a Binary Tree

The problem requires finding the second minimum value in a special binary tree where each node has either two or zero children. The root's value is always the smaller of its two children's values. We need to output the second smallest unique value in the entire tree, or -1 if no such value exists.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

671. Second Minimum Node In a Binary Tree

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 0
Acceptance rate: 42.8%


Problem Breakdown

The problem requires finding the second minimum value in a special binary tree where each node has either two or zero children. The root’s value is always the smaller of its two children’s values. We need to output the second smallest unique value in the entire tree, or -1 if no such value exists.

Inputs:

  • A non-empty binary tree with nodes having non-negative integer values.
  • Each node has either two or zero children.
  • The root’s value is the minimum of its two children’s values.

Outputs:

  • An integer representing the second smallest unique value in the tree, or -1 if it doesn’t exist.

Implicit Constraints/Edge Cases:

  • If all nodes have the same value, the output should be -1.
  • The tree can have up to 25 nodes.
  • Node values are within the range [1, 2^31 - 1].

Intuition

A brute-force approach would involve traversing the entire tree to collect all unique node values and then sorting them to find the second smallest. However, this approach is inefficient in terms of both time (O(n log n) due to sorting) and space (O(n) for storing unique values).

The key insight is that since each parent node’s value is the minimum of its children’s values, we can leverage this property to avoid unnecessary traversals. Specifically:

  • If a child node has a different value from its parent, it must be a candidate for the second minimum.
  • We can perform a depth-first search (DFS) starting from the root and keep track of the smallest and second smallest unique values encountered.

Approach

  1. Initialize two variables, first_min and second_min, to store the smallest and second smallest unique values. Set first_min to the root’s value and second_min to infinity.
  2. Perform a DFS traversal of the tree:
    • If a node’s value is greater than first_min and less than second_min, update second_min.
    • Recursively traverse the left and right children if they exist.
  3. After the traversal, check if second_min was updated from its initial value (infinity). If it was, return second_min; otherwise, return -1.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack used for DFS traversal. In the worst case, h can be n (for a skewed tree).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findSecondMinimumValue(root: TreeNode) -> int:
    first_min = root.val
    second_min = float('inf')
    
    def dfs(node):
        nonlocal second_min
        if node is None:
            return
        if first_min < node.val < second_min:
            second_min = node.val
        dfs(node.left)
        dfs(node.right)
    
    dfs(root)
    return second_min if second_min != float('inf') else -1

Edge Cases Handled

  • All nodes have the same value: The function will correctly return -1 since second_min remains infinity.
  • Tree with a single node: The function will correctly return -1 as there is no second minimum value.
  • Skewed tree (completely unbalanced): The DFS traversal handles this by only visiting necessary nodes, maintaining O(n) time complexity.