Verify Preorder Serialization of a Binary Tree (medium)

Problem Statement

You are given a string called preorder that represents the serialization of a binary tree.

This serialization string is created using a preorder traversal, where each node's value is recorded if it is a non-null node. Otherwise, we record using a sentinel value such as '#'.

The string preorder contains only integers and the character '#', separated by commas. The format is always valid, so there will be no cases like two consecutive commas (e.g., "1,,4").

Return true, if this string is a valid serialization of a binary tree. Otherwise, return false

.....

Like the course? Get enrolled and start learning!

Dakshesh Jain

· a year ago

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        available_slots = 1 # for root node

        for node in nodes:
            # since node is processed 
            available_slots -= 1

            # negative slots can't be possible
            if available_slots < 0:
                return False

            # since this is not a null node it will create 2 slots
            if node != "#":
                available_slots += 2
        
        # finally checking if all slots are exactly filled
        return available_slots == 0