algoadvance

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’s value is either equal to or greater than the values in its children. Find the second minimum value in the set made of all the nodes’ values in the whole tree.

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

Clarifying Questions

  1. What is a special binary tree?
    • A special binary tree in this context means that each node’s value is either equal to or greater than the values in its children.
  2. Can the tree have duplicate values?
    • Yes, the tree can have duplicate values.
  3. What if the root node is the only node in the tree?
    • If the root node is the only node in the tree, then there isn’t a second minimum value. Hence, the output should be -1.
  4. What is the maximum number of nodes in the tree?
    • This isn’t explicitly stated, but it’s reasonable to assume it fits within typical constraint limits for a binary tree in competitive programming, i.e., up to around (10^4) nodes.

Strategy

  1. In-order Traversal or Level Order Traversal:
    • Traverse the entire tree while collecting all unique values into a set.
  2. Finding the Minimum and Second Minimum:
    • Ensure the first minimum is the root value.
    • Iterate through the collected values to find the second smallest distinct value.
  3. Edge Case:
    • If all the values are the same, there is no second minimum, so return -1.

The traversal ensures that all elements are visited, and using a set naturally ensures uniqueness.

Time Complexity

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findSecondMinimumValue(root: TreeNode) -> int:
    if not root:
        return -1
    
    # This set will store unique values
    unique_values = set()
    
    def traverse(node):
        if node:
            # Add the value of the current node to the set
            unique_values.add(node.val)
            traverse(node.left)
            traverse(node.right)
    
    # Perform the traversal starting from the root
    traverse(root)
    
    # Convert the set to a sorted list
    unique_values = list(unique_values)
    
    if len(unique_values) <= 1:
        return -1

    first_min = min(unique_values)
    second_min = float('inf')
    
    for value in unique_values:
        if first_min < value < second_min:
            second_min = value
    
    return second_min if second_min < float('inf') else -1

This solution ensures that we efficiently find and return the second smallest node value if it exists, or -1 otherwise.

Try our interview co-pilot at AlgoAdvance.com