How do you solve Second Minimum Node In a Binary Tree on LeetCode?

Second Minimum Node In a Binary Tree (LeetCode #671) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The binary tree structure allows us to leverage the properties of node values for efficient traversal.

What is the brute force solution for Second Minimum Node In a Binary Tree?

The brute force approach for Second Minimum Node In a Binary Tree is Brute Force, with O(n²) time complexity and O(n) space complexity. We can traverse the entire tree and collect all node values in a list. Then, we can sort this list to find the second minimum value. This approach is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Second Minimum Node In a Binary Tree?

Second Minimum Node In a Binary Tree uses the following concepts: Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Tree Traversal.

What are the interview tips for Second Minimum Node In a Binary Tree?

Clearly explain your thought process while coding. Consider edge cases, such as trees with all identical values. Practice writing both brute force and optimal solutions to strengthen understanding.

What are common mistakes when solving Second Minimum Node In a Binary Tree?

Students often forget to handle the case where there is no second minimum value. Confusing the traversal order can lead to incorrect minimum value updates.

#671

Second Minimum Node In a Binary Tree

Easy

TreeDepth-First SearchBinary TreeDepth-First SearchTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

Instead of collecting all values, we can traverse the tree and keep track of the minimum and second minimum values directly, which is more efficient.

⚙️

Algorithm

5 steps

1Step 1: Initialize two variables, min1 (minimum) and min2 (second minimum) to -1.
2Step 2: Traverse the tree using DFS.
3Step 3: For each node, if its value is less than min1, update min2 to min1 and min1 to the current node's value.
4Step 4: If the current node's value is greater than min1 but less than min2, update min2.
5Step 5: At the end of traversal, return min2 if it's still greater than -1; otherwise, return -1.

solution.py21 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def findSecondMinimumValue(self, root: TreeNode) -> int:
10        min1, min2 = float('inf'), float('inf')
11        def dfs(node):
12            if node:
13                if node.val < min1:
14                    min2 = min1
15                    min1 = node.val
16                elif min1 < node.val < min2:
17                    min2 = node.val
18                dfs(node.left)
19                dfs(node.right)
20        dfs(root)
21        return min2 if min2 < float('inf') else -1

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(1) since we only use a fixed amount of extra space for the two minimums.

1The binary tree structure allows us to leverage the properties of node values for efficient traversal.
2Directly tracking minimums avoids unnecessary sorting and storage.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.