Second Minimum Node In a Binary Tree solution and explanation
9 more videos on this problem
Second Minimum Node In a Binary Tree | Leetcode 671nETSETOS · 11:46 · 4K views
Second Minimum Node In a Binary Tree | LEETCODE - 671 | Easy solutionhi-malik · 5:36 · 2K views
671. Second Minimum Node In a Binary Tree (Leetcode Easy)Programming Live with Larry · 7:11 · 911 views
Second Minimum Node In a Binary Tree | Leetcode 671 | Amazon Google Facebook interview questionSuper Lazy Coder · 7:05 · 809 views
LeetCode 671. Second Minimum Node In a Binary Tree Solution Explained - JavaAlgorithms and Data Structures Course · 7:33 · 787 views
Second Minimum Node In a Binary Tree LeetCode:671Tensordroid · 5:21 · 694 views
671. Second Minimum Node In a Binary Tree | Leetcode | PythonAbdullah Arshed · 2:27 · 212 views
LeetCode - Second Minimum Node In a Binary Treeciaociao_o · 9:25 · 202 views
LeetCode 671 | Second Minimum Node In a Binary Tree | JavaSleepy Cracker · 3:06 · 183 views
Leetcode solving: 671. Second Minimum Node In a Binary TreeMath Geeks · 2:23 · 109 views
The problem
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 - 1root.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.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def findSecondMinimumValue(self, root: TreeNode) -> int:
self.first = root.val
self.second = -1
def dfs(node):
if node:
if self.first < node.val < self.second or self.second == -1:
self.second = node.val
dfs(node.left)
dfs(node.right)
dfs(root)
return self.secondclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int first;
private int second = -1;
public int findSecondMinimumValue(TreeNode root) {
first = root.val;
dfs(root);
return second;
}
private void dfs(TreeNode node) {
if (node != null) {
if (first < node.val && (second == -1 || node.val < second)) {
second = node.val;
}
dfs(node.left);
dfs(node.right);
}
}
}#include <iostream>
#include <limits.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void dfs(TreeNode* root, int &min, int &second_min) {
if (!root) return;
if (root->val != min) {
if (second_min == -1 || root->val < second_min) {
second_min = root->val;
}
}
dfs(root->left, min, second_min);
dfs(root->right, min, second_min);
}
int findSecondMinimumValue(TreeNode* root) {
if (!root) return -1;
int min = root->val;
int second_min = -1;
dfs(root, min, second_min);
return second_min;
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var findSecondMinimumValue = function(root) {
let first = root.val;
let second = -1;
function dfs(node) {
if (node) {
if (first < node.val && (second === -1 || node.val < second)) {
second = node.val;
}
dfs(node.left);
dfs(node.right);
}
}
dfs(root);
return second;
};#include <stdio.h>
#include <limits.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void dfs(struct TreeNode* root, int *min, int *second_min) {
if (!root) return;
if (root->val != *min) {
if (*second_min == -1 || root->val < *second_min) {
*second_min = root->val;
}
}
dfs(root->left, min, second_min);
dfs(root->right, min, second_min);
}
int findSecondMinimumValue(struct TreeNode* root) {
if (!root) return -1;
int min = root->val;
int second_min = -1;
dfs(root, &min, &second_min);
return second_min;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int first;
private int second = -1;
public int FindSecondMinimumValue(TreeNode root) {
first = root.val;
DFS(root);
return second;
}
private void DFS(TreeNode node) {
if (node != null) {
if (first < node.val && (second == -1 || node.val < second)) {
second = node.val;
}
DFS(node.left);
DFS(node.right);
}
}
}In the Python implementation, a recursive DFS is used, where the first and second minimums are initialized, and a helper function is used to explore the tree. It updates the second minimum when it encounters a node value that's a valid candidate.
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(h), recursion stack height (h).
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.
import collections
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def findSecondMinimumValue(self, root: TreeNode) -> int:
if not root:
return -1
first = root.val
second = -1
queue = collections.deque([root])
while queue:
node = queue.popleft()
if first < node.val < second or second == -1:
second = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return secondimport java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int findSecondMinimumValue(TreeNode root) {
if (root == null) return -1;
int first = root.val;
int second = -1;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.val > first && (second == -1 || node.val < second)) {
second = node.val;
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return second;
}
}#include <iostream>
#include <limits.h>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int findSecondMinimumValue(TreeNode* root) {
if (!root) return -1;
int first = root->val, second = -1;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode *node = q.front(); q.pop();
if (node->val > first && (second == -1 || node->val < second)) {
second = node->val;
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return second;
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var findSecondMinimumValue = function(root) {
if (!root) return -1;
let first = root.val;
let second = -1;
let queue = [root];
while (queue.length > 0) {
let node = queue.shift();
if (node.val > first && (second === -1 || node.val < second)) {
second = node.val;
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return second;
};#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int findSecondMinimumValue(TreeNode* root) {
if (!root) return -1;
int first = root->val, second = -1;
TreeNode **queue = (TreeNode **)malloc(100 * sizeof(TreeNode*));
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode *node = queue[front++];
if (node->val > first && (second == -1 || node->val < second)) {
second = node->val;
}
if (node->left) queue[rear++] = node->left;
if (node->right) queue[rear++] = node->right;
}
free(queue);
return second;
}using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int FindSecondMinimumValue(TreeNode root) {
if (root == null) return -1;
int first = root.val;
int second = -1;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
TreeNode node = queue.Dequeue();
if (node.val > first && (second == -1 || node.val < second)) {
second = node.val;
}
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
return second;
}
}In the Python code, a BFS approach is employed using a deque. The process involves enqueuing nodes as they are discovered, with conditions checking to ascertain and possibly update the second minimum candidate based on node values.
Time Complexity: O(n).
Space Complexity: O(w) where w is the maximum number of nodes in a level within the queue.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findSecondMinimumValue(root *TreeNode) int {
ans, v := -1, root.Val
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
dfs(root.Right)
if root.Val > v {
if ans == -1 || ans > root.Val {
ans = root.Val
}
}
}
dfs(root)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) Approach | Time Complexity: O(n), where n is the number of nodes. |
| Iterative Breadth-First Search (BFS) Approach | Time Complexity: O(n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When 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 |
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.