LeetCode 671 - Second Minimum Node In a Binary Tree

The problem provides a special binary tree where each node either has zero or two children, and every internal node has a value equal to the smaller value among its two children.

leetcodeeasytreedepth-first-searchbinary-tree

LeetCode Problem 671

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem provides a special binary tree where each node either has zero or two children, and every internal node has a value equal to the smaller value among its two children. This property guarantees that the root contains the minimum value in the tree, since the root is always the smallest among its immediate children, and by recursion, the smallest of the entire tree.

The task is to find the second minimum value among all nodes. If all nodes share the same value, there is no second minimum, and the function should return -1.

The input is a binary tree with 1 to 25 nodes, and node values range from 1 up to $2^{31}-1$. The tree property ensures the smallest value is always at the root, which simplifies the search for the second smallest value.

Key edge cases include trees where all nodes are equal, trees with only one branch containing larger values, and trees with exactly two levels.

Approaches

A brute-force approach would be to traverse all nodes, collect all values in a set to remove duplicates, sort them, and pick the second smallest. This guarantees correctness but is unnecessary due to the special tree property. Its time complexity is O(n log n) due to sorting, and space complexity is O(n) for storing all unique values.

The optimal approach leverages the fact that the root contains the smallest value. Any second minimum must be strictly larger than the root. We can recursively traverse the tree and ignore nodes equal to the root unless they contain children. Whenever a node’s value is greater than the root, we record it as a candidate for the second minimum. This avoids unnecessary storage or sorting and reduces complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Collect all values, sort, pick second minimum
Optimal O(n) O(h) DFS traversal, only track candidates greater than root, h is tree height

Algorithm Walkthrough

  1. Initialize a variable root_val to store the value of the root. This is the minimum in the tree.
  2. Define a recursive helper function that traverses the tree:
  • If the node is None, return -1.
  • If the node’s value is greater than root_val, return this value as a candidate.
  • Otherwise, recursively call the helper on the left and right children.
  1. Combine the left and right results:
  • If both are -1, return -1.
  • If one is -1, return the other.
  • If neither is -1, return the smaller one.
  1. Call the helper on the root and return its result.

Why it works: Because the smallest value is guaranteed at the root, the algorithm only considers values strictly larger than the root. Recursive comparisons ensure the smallest such candidate is returned. The tree property guarantees that a larger value will not appear above a smaller one, preserving correctness.

Python Solution

# 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:
        if not root:
            return -1
        
        root_val = root.val
        
        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return -1
            if node.val > root_val:
                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)

The dfs function recursively checks each node. If the node value is larger than the root, it becomes a candidate. If a node equals the root, we continue searching its children. The min comparison at the end ensures the smallest candidate greater than the root is chosen.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findSecondMinimumValue(root *TreeNode) int {
    if root == nil {
        return -1
    }
    
    rootVal := root.Val
    
    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return -1
        }
        if node.Val > rootVal {
            return node.Val
        }
        
        left := dfs(node.Left)
        right := dfs(node.Right)
        
        if left == -1 {
            return right
        }
        if right == -1 {
            return left
        }
        if left < right {
            return left
        }
        return right
    }
    
    return dfs(root)
}

In Go, nil represents missing children. The recursive structure mirrors the Python version. Comparison logic explicitly returns the smaller non--1 value.

Worked Examples

Example 1: [2,2,5,null,null,5,7]

Node dfs Result Reason
5 (left leaf) 5 > root_val 2
7 (right leaf) 7 > root_val 2
5 (parent) min(5, 7) = 5 Choose smaller candidate
Root 2 min(left, right) = 5 Second minimum

Output: 5

Example 2: [2,2,2]

Node dfs Result Reason
Left leaf 2 -1 = root_val
Right leaf 2 -1 = root_val
Root 2 min(-1, -1) = -1 No second minimum

Output: -1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited once during DFS
Space O(h) Recursion stack up to tree height h, at most O(n) in skewed tree

The optimal algorithm efficiently traverses only once and does not need additional storage beyond the recursion stack.

Test Cases

# Provided examples
assert Solution().findSecondMinimumValue(TreeNode(2, TreeNode(2), TreeNode(5, TreeNode(5), TreeNode(7)))) == 5  # Example 1
assert Solution().findSecondMinimumValue(TreeNode(2, TreeNode(2), TreeNode(2))) == -1  # Example 2

# Single node tree
assert Solution().findSecondMinimumValue(TreeNode(1)) == -1  # Only root

# Two-level tree
assert Solution().findSecondMinimumValue(TreeNode(1, TreeNode(1), TreeNode(3))) == 3  # Right child is second min

# All nodes equal
assert Solution().findSecondMinimumValue(TreeNode(4, TreeNode(4), TreeNode(4, TreeNode(4), TreeNode(4)))) == -1  # No second min

# Larger values
assert Solution().findSecondMinimumValue(TreeNode(1, TreeNode(1), TreeNode(2))) == 2  # Minimal tree with second min
Test Why
[2,2,5,null,null,5,7] Basic case with second minimum in deeper node
[2,2,2] All equal nodes, no second minimum
[1] Single node, no second minimum
[1,1,3] Second minimum is a direct child
[4,4,4,4,4] Larger tree, all equal, tests -1
[1,1,2] Minimal case with second minimum present

Edge Cases

Single-node tree: A tree with only one node should return -1 because no second value exists. The algorithm handles this because the DFS immediately returns -1 for missing children.

All nodes equal: Trees where every node has the same value should return -1. Since DFS only considers values greater than the root, it will not find any candidates, correctly returning -1.

Second minimum deeper in tree: In some trees, the second minimum may not be a direct child of the root. For instance, in [2,2,5,null,null,5,7], DFS ensures that deeper candidates like 5 and 7 are correctly compared to find the smallest one greater than the root. This demonstrates the need to traverse the full tree rather than stopping at the first larger child.