{x}
blog image

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.

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.

Solution Explanation:

This problem asks to find the second minimum value in a special binary tree. The special property of this tree is that each node's value is the minimum of its children's values. This property significantly simplifies the search for the second minimum.

The solution uses Depth-First Search (DFS) to traverse the tree. The algorithm maintains two variables:

  • ans: Stores the current second minimum value found. Initialized to -1, indicating no second minimum found yet.
  • v: Stores the minimum value in the tree (the root's value). We know this because of the tree's special property.

The dfs function recursively visits each node. If a node's value (root.val) is greater than the minimum value (v), it means we've found a candidate for the second minimum. We update ans accordingly, choosing the smaller value between the current ans and the node's value.

Time Complexity Analysis:

The DFS algorithm visits each node in the tree exactly once. Therefore, the time complexity is O(N), where N is the number of nodes in the tree.

Space Complexity Analysis:

The space complexity depends on the recursion depth. In the worst case (a skewed tree), the depth is O(N). In the best case (a balanced tree), the depth is O(log N). Thus, the space complexity is O(N) in the worst case and O(log N) in the best case. However, we can also consider the space used by the recursive call stack as part of the space complexity, leading to O(H) where H is the height of the tree.

Code Explanation (Python):

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root:
                dfs(root.left)
                dfs(root.right)
                nonlocal ans, v  # access variables from the outer scope
                if root.val > v:
                    ans = root.val if ans == -1 else min(ans, root.val)
 
        ans, v = -1, root.val  # Initialize ans and v
        dfs(root)
        return ans

The Python code efficiently implements the described algorithm. The nonlocal keyword is crucial; it allows the inner dfs function to modify the ans and v variables from the outer scope. The conditional assignment ans = root.val if ans == -1 else min(ans, root.val) concisely handles the case where ans is initially -1.

The other languages (Java, C++, Go, JavaScript) follow the same logic, adapting the syntax to their respective language features. Note that the nonlocal keyword is not needed in these languages because variable scope is handled differently. In Java, C++, and Go, the ans variable is declared and updated within the dfs function, but it's a member variable of the Solution class. In JavaScript, ans is declared in the outer scope and accessed in the inner function without special keywords.

In all examples, the initial value of ans is set to -1, indicating no second minimum initially. The algorithm then recursively traverses the tree, updating ans whenever a node with a value greater than the minimum (v) is encountered. The final ans value represents the second minimum value in the tree or -1 if no such value exists.