Problem Description

You are given a special binary tree with the following properties:

1. Every node has exactly 2 children or no children (it's either a leaf node with 0 children or an internal node with 2 children)

2. All node values are non-negative integers

3. Parent-child value relationship: If a node has two children, its value equals the minimum of its two children's values. In other words, parent.val = min(left_child.val, right_child.val)

Your task is to find the second smallest value among all the values in the entire tree.

Key Points:

• The root node will always contain the smallest value in the tree (due to the min-heap property)
• You need to find the next smallest distinct value after the root's value
• If there is no second minimum value (for example, if all nodes have the same value), return -1

Example scenarios:

• If the tree has values like [2, 2, 5, 5, 7], the minimum is 2 and the second minimum is 5
• If all nodes have the same value, there's no second minimum, so return -1

The solution uses a depth-first search (DFS) to traverse the tree and track the smallest value greater than the root's value. Since the root contains the global minimum, any value larger than the root is a candidate for the second minimum. The algorithm compares all such candidates and returns the smallest one.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure with nodes connected in a hierarchical manner without cycles.

DFS

• Conclusion reached: Since we're dealing with a tree structure, the flowchart directly points us to use DFS (Depth-First Search).

The flowchart analysis confirms that DFS is the appropriate approach for this problem. This makes sense because:

1. We need to traverse the entire tree to examine all node values
2. We're looking for a specific value (second minimum) that could be anywhere in the tree
3. DFS allows us to systematically explore each branch of the tree from root to leaves
4. The tree structure naturally lends itself to recursive DFS implementation

In the given solution, DFS is implemented recursively to:

• Visit every node in the tree
• Compare each node's value with the root value (which is the minimum)
• Track the smallest value that is greater than the root value (which becomes our second minimum)

Conclusion: The flowchart correctly guides us to use DFS for traversing the binary tree to find the second minimum value.

Intuition

The key insight comes from understanding the special property of this tree: the root always contains the minimum value of the entire tree. This is because each parent node equals the minimum of its children, creating a min-heap-like structure where values can only increase or stay the same as we go down the tree.

Since we know the root is the smallest value, finding the second minimum becomes straightforward: we need to find the smallest value that is strictly greater than the root's value.

Think about it this way:

• The root value root.val is guaranteed to be the global minimum
• Any node with value > root.val is a candidate for being the second minimum
• We just need to find the smallest among all these candidates

Why does DFS work perfectly here? Because we need to examine every single node in the tree to ensure we don't miss any potential second minimum value. A node deep in the tree might have the second smallest value, so we can't stop early.

The algorithm naturally follows:

1. Remember the root value as our baseline (the minimum)
2. Traverse the entire tree using DFS
3. For each node encountered, if its value is greater than the root value, it's a candidate
4. Keep track of the smallest candidate seen so far
5. After traversing all nodes, the smallest candidate is our answer

The beauty of this approach is its simplicity - we're essentially doing a single pass through the tree looking for the smallest value that's bigger than what we already know is the minimum. If we never find such a value (all nodes equal the root), we return -1.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS traversal with a simple tracking mechanism for the second minimum value.

Data Structures Used:

• Two variables: ans to store the second minimum (initialized to -1) and v to store the root value (the global minimum)
• The nonlocal keyword in Python to modify outer scope variables from within the nested function

Algorithm Steps:

1. Initialize tracking variables:

   ans, v = -1, root.val

   • v stores the root value (guaranteed minimum)
   • ans starts at -1 (our default return value if no second minimum exists)

2. Define the DFS function:

   def dfs(root):
       if root:
           dfs(root.left)
           dfs(root.right)
           # Process current node after visiting children

   The DFS recursively visits left subtree, then right subtree, then processes the current node.

3. Core logic for finding second minimum:

   if root.val > v:
       ans = root.val if ans == -1 else min(ans, root.val)

   • Only consider nodes with values greater than the minimum (root.val > v)
   • If ans is still -1 (first candidate found), set it to the current node's value
   • Otherwise, keep the smaller value between the current ans and the new candidate

Why this works:

• Since we traverse every node, we're guaranteed to examine all possible candidates
• The condition root.val > v filters out all nodes equal to the minimum
• The min() operation ensures we always keep track of the smallest valid candidate
• If no node has a value greater than the root, ans remains -1

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack.

Example Walkthrough

Let's trace through the algorithm with a concrete example tree:

       2
      / \
     2   5
        / \
       5   7

Step 1: Initialize variables

• ans = -1 (no second minimum found yet)
• v = 2 (root value, which is the global minimum)

Step 2: Start DFS traversal from root (value = 2)

The DFS visits nodes in this order:

1. Visit root (2)

   • Recursively visit left child

2. Visit left child (2)

   • This is a leaf, so no children to visit
   • Check: Is 2 > v (i.e., 2 > 2)? No, so skip this node
   • Return to parent

3. Back at root, now visit right child (5)

   • Recursively visit its left child

4. Visit node (5) - left child of node (5)

   • This is a leaf
   • Check: Is 5 > v (i.e., 5 > 2)? Yes!
   • Since ans == -1, set ans = 5
   • Return to parent

5. Back at node (5), visit right child (7)

   • This is a leaf
   • Check: Is 7 > v (i.e., 7 > 2)? Yes!
   • Since ans == 5, compute min(5, 7) = 5
   • Keep ans = 5
   • Return to parent

6. Back at node (5) - process this node

   • Check: Is 5 > v (i.e., 5 > 2)? Yes!
   • Since ans == 5, compute min(5, 5) = 5
   • Keep ans = 5

Step 3: DFS complete, return result

• Return ans = 5

The second smallest value in the tree is 5.

Key observations from this walkthrough:

• Node with value 2 (equal to root) was skipped
• All nodes with values greater than 2 were considered (both 5s and the 7)
• The algorithm correctly identified 5 as the smallest value greater than the minimum (2)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree. The DFS traversal visits each node exactly once, performing constant time operations at each node (comparison and assignment operations).

Space Complexity: O(h) where h is the height of the binary tree. This space is used by the recursive call stack during the DFS traversal. In the worst case of a skewed tree, this could be O(n), while in the best case of a balanced tree, it would be O(log n). The additional space used for the variables ans and v is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Early Termination Optimization Leading to Incorrect Results

A common pitfall is trying to optimize the traversal by stopping early when we think we've found the answer. For example:

Incorrect Approach:

def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
    def dfs(node):
        if not node:
            return
      
        nonlocal second_min, first_min
      
        # WRONG: Early termination when we find a value > first_min
        if node.val > first_min:
            second_min = node.val
            return  # Stop searching - THIS IS WRONG!
      
        dfs(node.left)
        dfs(node.right)
  
    second_min = -1
    first_min = root.val
    dfs(root)
    return second_min

Why this fails: Due to the tree's special property where parent.val = min(left.val, right.val), the second minimum value might not be at the shallowest level. Consider this tree:

      2
     / \
    2   5
       / \
      5   3

If we stop at the first node with value > 2 (which is 5), we miss the actual second minimum value 3.

Solution: Always traverse the entire tree to ensure we find the global second minimum.

2. Incorrect Handling of Duplicate Values

Another pitfall is not properly handling trees where multiple nodes have the minimum value:

Incorrect Approach:

def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
    def dfs(node):
        if not node:
            return
      
        nonlocal second_min
      
        # WRONG: Not checking if value is actually greater than minimum
        if node.val != root.val:  # This seems logical but...
            if second_min == -1:
                second_min = node.val
            else:
                second_min = min(second_min, node.val)
      
        dfs(node.left)
        dfs(node.right)

Why this might seem correct but has issues: While node.val != root.val is equivalent to node.val > root.val in this specific tree structure (since parent = min of children), using inequality comparison makes the logic clearer and more maintainable.

3. Forgetting the Tree's Special Properties

A critical pitfall is attempting pruning optimizations without fully understanding the tree structure:

Incorrect Pruning:

def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
    def dfs(node):
        if not node:
            return
      
        nonlocal second_min, first_min
      
        # WRONG: Assuming we can skip subtrees
        if node.val == first_min:
            # Skip this subtree - INCORRECT!
            return
      
        if node.val > first_min:
            second_min = node.val if second_min == -1 else min(second_min, node.val)
      
        dfs(node.left)
        dfs(node.right)

Why this fails: Even if a node has the minimum value, its children might have different values that could be candidates for the second minimum. The tree property only guarantees parent = min(children), not that all descendants have the same value.

Correct Solution: The provided solution avoids all these pitfalls by:

1. Traversing the entire tree without early termination
2. Using clear comparison logic (node.val > first_min)
3. Not making assumptions about subtrees based on parent values