Second Minimum Node In a Binary Tree - Practice Coding Problems

Second Minimum Node In a Binary Tree - Problem

Given a non-empty special binary tree consisting of nodes with non-negative values, where each node in this tree has exactly two or zero child nodes. If the node has two child nodes, then this node's value is the smaller value among its two child 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' values in the whole tree. If no such second minimum value exists, output -1 instead.

Input & Output

Example 1 — Basic Case

$ Input: root = [2,2,3]

› Output: 3

💡 Note: The tree has values {2, 3}. The minimum is 2 and the second minimum is 3.

Example 2 — No Second Minimum

$ Input: root = [2,2,2]

› Output: -1

💡 Note: All nodes have the same value 2, so there is no second minimum value.

Example 3 — Larger Tree

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

› Output: 5

💡 Note: The tree has values {2, 5, 7}. The minimum is 2 and the second minimum is 5.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Special binary tree where parent = min(left, right)

Tree Property

Root is always minimum, find next smallest

Output

Second minimum value or -1 if none exists

Key Takeaway

🎯 Key Insight: The root is always the minimum due to the tree property, so we only need to find the smallest value greater than the root value.

Asked in

Li LinkedIn 15 a Amazon 12 G Google 8

The key insight is that the root is always the minimum value due to the tree property. We only need to find the smallest value greater than the root. The optimal approach uses DFS with a single variable to track the second minimum in O(n) time and O(h) space.

Common Approaches

Approach	Time	Space	Notes
✓ Collect All Values	O(n log n)	O(n)	Traverse the entire tree, collect all unique values, sort them, and return the second element
Single Pass Optimized	O(n)	O(h)	Find second minimum in one pass by tracking the smallest value greater than root
DFS with Pruning	O(n)	O(h)	Use DFS but prune branches that cannot contain the second minimum value

Collect All Values — Algorithm Steps

Perform DFS/BFS traversal of the entire tree
Add all node values to a set to avoid duplicates
Convert set to sorted list
Return second element if list has at least 2 elements, otherwise -1

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit every node and collect values

Remove Duplicates

Use set to keep only unique values

Sort and Pick

Sort values and return second element

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

void dfs(struct TreeNode* node, int* values, int* count, int* capacity) {
    if (!node) return;
    
    // Check if value already exists
    int exists = 0;
    for (int i = 0; i < *count; i++) {
        if (values[i] == node->val) {
            exists = 1;
            break;
        }
    }
    
    if (!exists) {
        if (*count >= *capacity) {
            *capacity *= 2;
            values = realloc(values, *capacity * sizeof(int));
        }
        values[(*count)++] = node->val;
    }
    
    dfs(node->left, values, count, capacity);
    dfs(node->right, values, count, capacity);
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(struct TreeNode* root) {
    if (!root) return -1;
    
    int capacity = 100;
    int* values = malloc(capacity * sizeof(int));
    int count = 0;
    
    dfs(root, values, &count, &capacity);
    
    qsort(values, count, sizeof(int), compare);
    
    int result = count >= 2 ? values[1] : -1;
    free(values);
    return result;
}

int main() {
    // For simplicity, we'll create a test tree manually
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = 2;
    root->left = malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Visit all n nodes O(n) plus sorting unique values O(k log k) where k ≤ n

⚡ Linearithmic

Space Complexity

O(n)

Set to store unique values and recursion stack for DFS

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

1.6K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Collect All Values — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler