#671

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Second Minimum Node In a Binary Tree

Find the second minimum node in a binary tree by traversing the tree and tracking state.

Problem Statement

Given a binary tree where each internal node is the smaller of its two children, find the second smallest unique value in the tree. If no such value exists, return -1.

The tree’s structure guarantees that each internal node holds the minimum of its two children, which simplifies the task of finding the second smallest value by tracking the minimum during traversal.

Examples

Example 1

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

Output: 5

The smallest value is 2, the second smallest value is 5.

Example 2

Input: root = [2,2,2]

Output: -1

The smallest value is 2, but there isn't any second smallest value.

Constraints

The number of nodes in the tree is in the range [1, 25].
1 <= Node.val <= 231 - 1
root.val == min(root.left.val, root.right.val) for each internal node of the tree.

Solution Approach

Binary Tree Traversal

To find the second minimum value, traverse the tree using Depth-First Search (DFS) while keeping track of the smallest and second smallest values found. This ensures an efficient solution while maintaining the tree's structure.

State Tracking During DFS

As the tree is traversed, maintain a set of values or two variables to track the smallest and second smallest values. If a node's value fits into this set, update accordingly. If no second value is found, return -1.

Early Exit Optimization

If a second minimum value is found during traversal, exit early to save computation. This avoids unnecessary traversals once the second smallest value is identified.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity are dependent on the traversal method. In the worst case, the solution requires O(N) time to traverse all nodes, where N is the number of nodes in the tree. Space complexity depends on the depth of the tree, O(H) where H is the tree's height for DFS.

What Interviewers Usually Probe

Does the candidate demonstrate an understanding of binary tree properties and DFS?
How efficiently does the candidate optimize the traversal process?
Can the candidate handle edge cases like trees without a second minimum value?

Common Pitfalls or Variants

Common pitfalls

Incorrectly assuming that there will always be a second minimum value in the tree.
Failure to correctly update the second minimum value during DFS traversal.
Not properly handling trees with repetitive values, which may lead to incorrect results.

Follow-up variants

Modify the problem to work on a generic binary tree, where nodes can have any number of children.
Expand the problem to return the k-th smallest value instead of just the second minimum.
Adapt the problem to handle non-unique nodes or nodes with different values in a more complex tree structure.

FAQ

What is the core idea behind solving the 'Second Minimum Node In a Binary Tree' problem?

The core idea is to traverse the tree using DFS while tracking the smallest and second smallest unique values.

How can I optimize the solution for large trees in this problem?

You can optimize by using early exit during traversal once the second minimum value is found.

Does the second minimum node always exist in the tree?

No, if all nodes are identical or there is only one unique value, the second minimum will not exist, and the answer should be -1.

Can the tree contain duplicate values?

Yes, the tree can contain duplicate values, which is why you must carefully track the smallest and second smallest values separately.

How does this problem relate to binary tree traversal patterns?

This problem emphasizes DFS for tree traversal while also incorporating state tracking, which is key to identifying the second smallest value efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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:
        def dfs(root):
            if root:
                dfs(root.left)
                dfs(root.right)
                nonlocal ans, v
                if root.val > v:
                    ans = root.val if ans == -1 else min(ans, root.val)

        ans, v = -1, root.val
        dfs(root)
        return ans

Continue Practicing

#669 trim a binary search tree #662 maximum width of binary tree #655 print binary tree