algoadvance

Leetcode 671. Second Minimum Node In a Binary Tree

Problem Statement

LeetCode Problem 671: Second Minimum Node In a Binary Tree

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.

Find the second minimum value in this tree. If no such second minimum value exists, return -1.

Clarifying Questions

1. What is the structure of the tree?
   • Each node has either 0 or 2 children.
2. Are the node values distinct?
   • No, multiple nodes can have the same value.
3. What is guaranteed about the tree?
   • The root node has the smallest value as per the property mentioned.
4. Can there be only one unique value in the tree?
   • Yes, if all nodes have the same value, return -1 as per the rules.

Strategy

1. Initial Checks:
   • If the tree is empty (though the problem states it is not), return -1.
   • If both left and right children are not present, return -1 since there can’t be a second minimum.
2. Traversal:
   • Use a Depth-First Search (DFS) to traverse the tree.
   • Track the minimum and the second minimum values.
3. Implementation Details:
   • Use a helper function to perform DFS.
   • Start the second minimum value as Long.MAX_VALUE (to handle larger secondary values).

Code

Here is the Java code to solve the problem:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return -1;
        }
        
        return dfs(root, root.val);
    }

    private int dfs(TreeNode node, int minValue) {
        if (node == null) {
            return -1;
        }
        
        if (node.val > minValue) {
            return node.val;
        }
        
        int left = dfs(node.left, minValue);
        int right = dfs(node.right, minValue);
        
        if (left > minValue && right > minValue) {
            return Math.min(left, right);
        }
        
        return left > minValue ? left : right;
    }
}

Time Complexity

• Time Complexity: The time complexity is (O(n)), where (n) is the number of nodes in the tree because we might visit each node once.

• Space Complexity: The space complexity is (O(h)), where (h) is the height of the tree due to the recursive call stack. In the worst-case scenario (a completely unbalanced tree), this could be (O(n)). For a balanced tree, it would be (O(\log n)).

This approach ensures that we efficiently determine the second minimum value by traversing the tree effectively while adhering to the problem’s requirements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?