We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Verify Preorder Serialization of a Binary Tree

Number: 331

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given a string of comma-separated values representing the preorder traversal of a binary tree (where null nodes are denoted by '#'), determine if the serialization is valid without reconstructing the tree.

Key Insights

  • Every non-null node provides two additional child slots.
  • The process starts with one available slot (for the root).
  • Each node (null or non-null) occupies one slot.
  • A non-null node (integer) creates two new slots, effectively increasing the slot count by one overall.
  • If at any point the available slot count becomes negative, the serialization is invalid.
  • A valid serialization will use exactly all available slots (ending with zero).

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes (tokens) in the input string.
Space Complexity: O(n) for storing the split tokens, though the core algorithm uses O(1) extra space.

Solution

The approach uses a slot counting mechanism. Start with one slot available for the root node. For each node in the preorder sequence, decrement the available slot by 1 because the node occupies a slot. If the node is non-null, add 2 slots (one for each child). At any point, if the available slot count becomes negative, the serialization is invalid. In the end, the serialization is valid if and only if no available slot remains (i.e., the count is zero).

Code Solutions

# Define the function to check valid serialization of a binary tree
def isValidSerialization(preorder: str) -> bool:
    # Start with one available slot for the root node
    available_slots = 1
    # Split the preorder string by commas to process each node
    nodes = preorder.split(',')
    
    # Iterate over each token in the preorder sequence
    for node in nodes:
        # Each node occupies one available slot
        available_slots -= 1
        # If available slots go negative, the serialization is invalid
        if available_slots < 0:
            return False
        # If the node is not null, it creates two additional slots (for its children)
        if node != "#":
            available_slots += 2
            
    # Valid if all slots have been perfectly filled
    return available_slots == 0

# Example usage:
print(isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"))
← Back to All Questions