LeetCode 671: Second Minimum Node In a Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 671: Second Minimum Node In a Binary Tree?

In LeetCode 671: Second Minimum Node In a Binary Tree, you’re given the root of a binary tree with a special property: each node has exactly two children (unless it’s a leaf), and its value is either the minimum of its children’s values or equal to one of them. Your task is to find the second smallest value in the entire tree, returning it as an integer, or -1 if no such value exists (e.g., all nodes are the same). For example, with root = [2, 2, 5, null, null, 5, 7], the smallest value is 2 (root), and the second smallest is 5, so you return 5. This problem tests your ability to traverse a tree and identify the second minimum efficiently, leveraging its special structure.

Problem Statement

• Input:
• root: Root node of a special binary tree.
• Output: An integer—second smallest value, or -1 if none exists.
• Rules:
• Each non-leaf node has two children.
• Node value = min(left, right) or equals one child.
• Find second smallest value among all nodes.

Constraints

• Number of nodes: 1 to 25.
• 1 ≤ Node.val ≤ 2³¹ - 1.

Examples

• Input: root = [2, 2, 5, null, null, 5, 7]
• Output: 5 (Smallest = 2, second = 5)
• Input: root = [2, 2, 2]
• Output: -1 (All values = 2, no second minimum)
• Input: root = [1, 1, 3, 1, 1, 3, 4, 3]
• Output: 3 (Smallest = 1, second = 3)

These examples set the tree—let’s solve it!

Understanding the Problem: Finding the Second Minimum

To solve LeetCode 671: Second Minimum Node In a Binary Tree in Python, we need to find the second smallest value in a binary tree where each node’s value is either the minimum of its children or equal to one of them. A brute-force approach—collecting all values and sorting—would be O(n log n), inefficient for small trees (n ≤ 25). Since the root is the smallest value and the tree has a special property, we can optimize by focusing on values larger than the root. We’ll use:

• Best Solution (DFS with Pruning): O(n) time, O(h) space—fast and elegant (h = height).
• Alternative Solution (BFS with Set): O(n) time, O(n) space—simple but less efficient.

Let’s start with the DFS solution, breaking it down for beginners.

Best Solution: DFS with Pruning

Why This Is the Best Solution

The DFS with pruning approach is the top choice for LeetCode 671 because it’s efficient—O(n) time with O(h) space—and leverages the tree’s property: the root is the smallest value, so we only need to search for the next smallest by pruning branches equal to the root. It fits constraints (n ≤ 25) perfectly and is intuitive once you see the pruning logic. It’s like diving into the tree and skipping the smallest branches to find the runner-up!

How It Works

Think of this as a value seeker:

• Step 1: Get Root Value:
• Root.val is the smallest value in the tree.
• Step 2: DFS Search:
• Recursively explore tree:
• If node.val = root.val, recurse on children (node itself isn’t second min).
• If node.val > root.val, it’s a candidate; compare with current second min.
• Prune: Skip further recursion if equal to root.val after checking children.
• Step 3: Track Second Minimum:
• Use a variable to update second smallest value.
• Step 4: Return Result:
• Return second min, or -1 if none found.

It’s like a tree scanner—prune and track!

Step-by-Step Example

Example: root = [2, 2, 5, null, null, 5, 7]

• Step 1: Root.val = 2, smallest = 2, second_min = float('inf').
• Step 2: DFS:
• Left (2):
• 2 = 2, recurse:
• Left (null): Return inf.
• Right (null): Return inf.
• Min(inf, inf) = inf.
• Right (5):
• 5 > 2, second_min = min(inf, 5) = 5, recurse:
• Left (5): 5 > 2, second_min = min(5, 5) = 5.
• Right (7): 7 > 2, second_min = min(5, 7) = 5.
• Return 5.
• Step 3: second_min = 5.
• Step 4: Return 5.
• Output: 5.

Example: root = [2, 2, 2]

• Step 1: Root.val = 2, second_min = inf.
• Step 2: DFS:
• Left (2): 2 = 2, recurse: null, null, return inf.
• Right (2): 2 = 2, recurse: null, null, return inf.
• Step 3: second_min = inf.
• Step 4: Return -1 (no second min).
• Output: -1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass 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: TreeNode) -> int:
        # Step 1: Initialize with root value
        if not root:
            return -1
        self.root_val = root.val
        self.second_min = float('inf')

        # Step 2: DFS to find second minimum
        def dfs(node):
            if not node:
                return
            # If equal to root, recurse on children
            if node.val == self.root_val:
                dfs(node.left)
                dfs(node.right)
            # If greater, update second minimum
            elif node.val > self.root_val:
                self.second_min = min(self.second_min, node.val)

        dfs(root)

        # Step 3: Return result
        return self.second_min if self.second_min != float('inf') else -1

• Lines 1-6: TreeNode class (standard).
• Lines 10-14: Init: Root value, second_min as infinity.
• Lines 17-25: DFS:
• Skip null, recurse if equal to root, update if greater.
• Line 28: Return: Second min or -1 if not found.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h = height).

This is like a value hunter—prune and find!

Alternative Solution: BFS with Set

Why an Alternative Approach?

The BFS with set approach uses breadth-first search—O(n) time, O(n) space. It’s simpler conceptually, collecting all values into a set and picking the second smallest, but uses more space and doesn’t leverage the tree’s property as effectively. It’s like sweeping the tree level-by-level to gather all possibilities!

How It Works

Picture this as a value gatherer:

• Step 1: BFS to collect values:
• Queue nodes, add values to a set.
• Step 2: Find second minimum:
• Convert set to sorted list, get second element.
• Step 3: Return result:
• Return -1 if fewer than 2 values.

It’s like a set collector—gather and sort!

Step-by-Step Example

Example: root = [2, 2, 5, null, null, 5, 7]

• Step 1: BFS:
• Queue: [2], [2, 5], [5, 7].
• Set: {2}, {2, 5}, {2, 5, 7}.
• Step 2: Sorted: [2, 5, 7], second = 5.
• Step 3: Return 5.
• Output: 5.

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        # Step 1: BFS to collect values
        if not root:
            return -1
        queue = deque([root])
        values = set()

        while queue:
            node = queue.popleft()
            values.add(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        # Step 2: Find second minimum
        sorted_vals = sorted(values)
        if len(sorted_vals) < 2:
            return -1

        # Step 3: Return second element
        return sorted_vals[1]

• Line 1: Import deque for queue.
• Lines 6-17: BFS:
• Queue nodes, collect unique values in set.
• Lines 20-24: Find second:
• Sort values, return second if exists, else -1.
• Time Complexity: O(n)—traverse all nodes.
• Space Complexity: O(n)—set and queue.

It’s a value sweeper—collect and pick!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n) time, O(h) space, leverages tree property.
• Cons: Recursive logic less obvious.
• BFS (Alternative):
• Pros: O(n) time, O(n) space, simple set approach.
• Cons: More space, less efficient.

DFS wins for efficiency.

Additional Examples and Edge Cases

• Input: [1]
• Output: -1.
• Input: [5, 5, 6]
• Output: 6.

DFS handles these well.

Complexity Breakdown

• DFS: Time O(n), Space O(h).
• BFS: Time O(n), Space O(n).

DFS is optimal for space.

Key Takeaways

• DFS: Pruned search—smart!
• BFS: Set collection—clear!
• Minimums: Trees are fun.
• Python Tip: DFS rocks—see Python Basics.

Final Thoughts: Find That Second Min

LeetCode 671: Second Minimum Node In a Binary Tree in Python is a fun tree challenge. DFS with pruning offers speed and elegance, while BFS with set provides a straightforward alternative. Want more? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 530: Minimum Absolute Difference in BST. Ready to explore? Head to Solve LeetCode 671 on LeetCode and find that second minimum today!