Preorder Serialization Verification of a Binary Tree (Deprecated)

Given a particular kind of preorder serialization of a binary tree, verify that it's valid. Tags: Recursion, Trees

Try It!

Discussion

Video

Solution

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # remember how many empty slots we have
        # non-null nodes occupy one slot but create two new slots
        # null nodes occupy one slot
        
        preorder = preorder.split(',')
        
        #initially we have one empty slot to put the root in it
        count = 1
        for node in preorder:
            
            # no empty slot to put the current node
            if count == 0:
                return False
                
            # a null node?
            if node == '#':
                # ocuppy slot
                count -= 1
            else:
                # use a slot, create 2 new slots
                count += 1
        
        #we don't allow empty slots at the end
        return count == 0