LeetCode 671: Second Minimum Node In a Binary Tree Solution

Master LeetCode problem 671 (Second Minimum Node In a Binary Tree), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

671. Second Minimum Node In a Binary Tree

Easy

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

To find the second minimum value in a special binary tree, we can perform a depth-first search (DFS) traversal, keeping track of the minimum and second minimum values encountered so far. The key observation is that the second minimum value must be a value from a leaf node that is different from the minimum value. Therefore, we can update the minimum and second minimum values while traversing the tree.

Initialize minValue and secondMinValue with Integer.MAX_VALUE.
Perform a DFS traversal of the binary tree.
At each node:
- If the node value is less than minValue, update secondMinValue and minValue.
- If the node value is between minValue and secondMinValue, update secondMinValue.
After the traversal, if secondMinValue is still Integer.MAX_VALUE, return -1. Otherwise, return secondMinValue.

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(h), where h is the height of the tree (recursive stack space).

Solution Code

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        int[] minValues = {Integer.MAX_VALUE, Integer.MAX_VALUE};
        dfs(root, minValues);
        return minValues[1] == Integer.MAX_VALUE ? -1 : minValues[1];
    }
    
    private void dfs(TreeNode node, int[] minValues) {
        if (node == null) return;
        
        if (node.val < minValues[0]) {
            minValues[1] = minValues[0];
            minValues[0] = node.val;
        } else if (node.val < minValues[1] && node.val != minValues[0]) {
            minValues[1] = node.val;
        }
        
        dfs(node.left, minValues);
        dfs(node.right, minValues);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 671 (Second Minimum Node In a Binary Tree)?

This page provides optimized solutions for LeetCode problem 671 (Second Minimum Node In a Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 671 (Second Minimum Node In a Binary Tree)?

The time complexity for LeetCode 671 (Second Minimum Node In a Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 671 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 671 in Java, C++, or Python.

Back to LeetCode Solutions