Second Minimum Node In a Binary Tree - Video Solutions

Problem Overview: You are given a special binary tree where every non-leaf node has exactly two children and its value equals the smaller of its two children's values. Because of this rule, the root always contains the smallest value in the entire tree. The task is to find the second smallest value across all nodes. If such a value does not exist, return -1.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

This approach traverses the tree using recursion and tracks the smallest value (which is always the root). During traversal, you look for the smallest value strictly greater than root.val. DFS works well because you can explore each subtree while maintaining the current candidate for the second minimum. When visiting a node, if its value is greater than the root value, it becomes a candidate and you compare it with the best answer found so far. Otherwise, you continue exploring its children. Since every node may need to be visited in the worst case, the time complexity is O(n). The recursion stack uses O(h) space where h is the tree height.

The key insight comes from the tree property: each parent equals the minimum of its children. That means any value greater than root.val automatically qualifies as a candidate for the second minimum. DFS naturally explores deeper branches first and is a clean way to implement this logic in problems involving Depth-First Search on a Binary Tree.

Approach 2: Iterative Breadth-First Search (BFS) (Time: O(n), Space: O(n))

The BFS approach uses a queue to traverse the tree level by level. Start by storing the root's value as the global minimum. While processing nodes from the queue, check if the node value is greater than the root value. If it is, update the second minimum candidate. If the node value equals the root value, its children might still contain larger values, so push them into the queue for further exploration. This ensures that all potential candidates are examined.

BFS processes nodes iteratively and avoids recursion. The time complexity remains O(n) because each node is processed once. The queue can store up to a full level of the tree, resulting in O(n) auxiliary space in the worst case. BFS is commonly used when working with general Tree traversals and is helpful when recursion depth could become large.

Recommended for interviews: The recursive DFS solution is usually preferred. It directly leverages the special property of the tree and keeps the code compact. Interviewers typically expect you to recognize that the root already holds the minimum value and then search for the smallest value greater than it using a full traversal. BFS is equally valid but slightly more verbose.