Skip to main content
Talentd

Second Minimum Node In a Binary Tree - Solution & Explanation

EasyTreeDepth-First SearchBinary Tree16 min readAsked at: Meta, LinkedIn
Practice this problem

Problem Statement

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

If no such second minimum value exists, output -1 instead.

 

 

Example 1:

Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: root = [2,2,2]
Output: -1
Explanation: 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.

Approach Overview

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.

Approach 1: Recursive Depth-First Search (DFS) Approach

This approach utilizes the recursive Depth-First Search (DFS) to traverse through the binary tree. Since each parent node value is equal to the minimum of its two children nodes, we need to traverse the tree to collect candidate values for the second minimum. This is done by keeping track of unique values found during traversal.

The C code implements a recursive DFS to explore each node, focusing on nodes with values different from the root (which holds the minimum value). It checks if a value smaller than the current second minimum is found, hence keeps updating the potential second minimum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. You visit each node once.
Space Complexity: O(h), where h is the height of the tree due to call stack usage in recursion.

Try this approach in the editor →

Approach 2: Iterative Breadth-First Search (BFS) Approach

This approach utilizes an iterative Breadth-First Search (BFS) using a queue to process nodes level by level. It maintains a minimum and a candidate for the second minimum. By using a level-order traversal, it systematically updates the second minimum whenever a node with a greater value than the minimum is discovered.

This C implementation uses a queue for BFS traversal. It starts with the root's value as the minimum and traverses level by level. Each node value is compared against the current minimum and potential second minimum, updating if conditions are met.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), processes each node once.
Space Complexity: O(w), where w is the maximum width of the tree (auxiliary space used by the queue).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Depth-First Search (DFS) Approach

Time Complexity: O(n), where n is the number of nodes in the tree. You visit each node once.
Space Complexity: O(h), where h is the height of the tree due to call stack usage in recursion.

Iterative Breadth-First Search (BFS) Approach

Time Complexity: O(n), processes each node once.
Space Complexity: O(w), where w is the maximum width of the tree (auxiliary space used by the queue).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Depth-First Search (DFS)O(n)O(h)Preferred interview solution; clean recursion that leverages tree properties
Iterative Breadth-First Search (BFS)O(n)O(n)Useful when avoiding recursion or when performing level-order traversal

Video Solution

Second Minimum Node In a Binary Tree | Leetcode 671 • nETSETOS • 4,133 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Second Minimum Node In a Binary Tree easy or hard?
LeetCode classifies this problem as Easy. The main challenge is recognizing the special property of the tree where each parent equals the smaller child. Once you understand that the root already holds the minimum value, the task becomes a straightforward tree traversal to find the next larger value.
Second Minimum Node In a Binary Tree Python/Java solution
Python and Java implementations typically perform a DFS starting from the root and track the smallest value greater than root.val. The same logic works across languages like C++, C#, and JavaScript. Each node is visited once, giving O(n) time complexity with minimal additional memory.
How to solve Second Minimum Node In a Binary Tree in O(n)?
Start by storing the root value as the smallest element. Traverse the tree using DFS or BFS and check each node's value. If a node value is greater than the root value, update the current second minimum candidate. Continue exploring nodes with the same value as the root since their children might contain larger values. This single traversal guarantees O(n) time.
What is the best approach for Second Minimum Node In a Binary Tree?
Recursive Depth-First Search (DFS) is the most common approach. Traverse the tree while tracking the smallest value greater than the root value. Because the root is guaranteed to contain the minimum element, any larger value encountered during traversal becomes a candidate for the second minimum. This approach runs in O(n) time with O(h) recursion space.
Is Second Minimum Node In a Binary Tree asked at Google/Amazon/Meta?
Tree traversal problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants often test understanding of DFS, BFS, and properties of binary trees. The problem is commonly used to evaluate traversal logic and candidate filtering during tree searches.
What data structure is used in Second Minimum Node In a Binary Tree?
The problem primarily uses a binary tree structure along with traversal techniques. DFS implementations rely on recursion (implicit stack), while BFS solutions use a queue to process nodes level by level. No additional complex data structures are required.
What is the time complexity of Second Minimum Node In a Binary Tree?
The optimal solution runs in O(n) time because every node may need to be visited once to verify whether it could be the second minimum. DFS or BFS traversal both achieve this complexity. Space complexity is O(h) for recursive DFS due to the call stack, or O(n) for BFS because of the queue.

Ready to solve this problem?

Practice Second Minimum Node In a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Kth Smallest Element in a BST