Second Minimum Node In A Binary Tree - Leetcode Solution

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.

Given the root of the binary tree, find the second minimum value.

If no such second minimum value exists, output -1 instead.

Solution:

We can solve this problem using a recursive algorithm. The basic idea is to traverse the tree in a depth-first manner and keep track of the smallest and second smallest values seen so far.

The first step is to check if the root node has two children. If not, it means the root node is the only node in the tree and there is no second minimum value.

If the root node has two children, we need to compare their values to find the smallest and second smallest values. Since the root node's value is the smaller of the two, we can ignore it and focus on the two children.

We can recursively traverse each child node and update the smallest and second smallest values seen so far. If a child node value is smaller than the smallest value, we update both smallest and second smallest values. If a child node value is larger than the smallest value but smaller than the current second smallest value, we update the second smallest value.

We can then return the second smallest value if it is different from the root node value. Otherwise, we can return -1 to indicate that no second minimum value exists.

Time Complexity:

The time complexity of the algorithm is O(n) since we need to visit each node once.

Space Complexity:

The space complexity of the algorithm is O(h), where h is the height of the tree. This is the space used by the recursive call stack. In the worst case, the binary tree is a skewed tree and the height is equal to the number of nodes. Therefore, the space complexity can be O(n) in the worst case.

Implementation:

Here is the Python implementation of the algorithm:

class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        # if root is a leaf node or None, return -1
        if not root or (not root.left and not root.right):
            return -1
        
        # find the smallest and second smallest values
        smallest = root.val
        second_smallest = float('inf')
        for child in [root.left, root.right]:
            # check if child value is smaller than smallest
            if child.val < smallest:
                second_smallest = smallest
                smallest = child.val
            # check if child value is greater than smallest but smaller than current second smallest
            elif child.val > smallest and child.val < second_smallest:
                second_smallest = child.val
        
        # recursively find the second smallest value in the children
        left_second_smallest = self.findSecondMinimumValue(root.left)
        right_second_smallest = self.findSecondMinimumValue(root.right)
        
        # take the minimum of the two second smallest values
        if left_second_smallest != -1 and right_second_smallest != -1:
            return min(left_second_smallest, right_second_smallest)
        elif left_second_smallest != -1:
            return left_second_smallest
        else:
            return right_second_smallest if right_second_smallest != -1 else -1

Note that the algorithm assumes that the binary tree is a special binary tree as described in the problem statement. Therefore, there is no need to check if a node has one child.

1