Verify Preorder Serialization Of A Binary Tree - Leetcode Solution

The problem "Verify Preorder Serialization of a Binary Tree" on LeetCode asks you to check if a given preorder traversal of a binary tree is valid or not. A valid preorder traversal must follow the rules of a binary tree and satisfy the following conditions:

• The number of nodes in the tree must be equal to the number of elements in the traversal string.
• The traversal string must represent a valid binary tree.
• The traversal string must represent a tree that is the same as the original tree for which this preorder traversal was taken.

To solve this problem, we can use a stack to keep track of the nodes that we have seen so far in the traversal string. We will also need to use a variable to keep track of the number of nodes that we have seen so far.

We can iterate through the characters in the traversal string one by one and perform the following checks:

• If the current character is a comma (','), we ignore it and move to the next character.
• If the current character is a number, we add it to the stack and increment the count of nodes seen so far.
• If the current character is a hash symbol ('#'), we know that this is a null node, so we do not add it to the stack. We do, however, increment the count of nodes seen so far.
• If the stack has two or more elements, and the two top elements are both hashes, we pop both of them from the stack and replace them with a single hash. This represents the fact that the two hashes were both children of the same parent node, which has now been processed.

After iterating through the entire traversal string, we should have only one element left in the stack, which should be a hash symbol. If this is the case, then the preorder traversal is valid and we can return true. Otherwise, the traversal is invalid and we can return false.

Here is the code in Python:

def isValidSerialization(preorder: str) -> bool: stack = [] nodes_seen = 0 for node in preorder.split(","): if node == "#": nodes_seen += 1 while len(stack) >= 2 and stack[-1] == "#" and stack[-2] != "#": stack.pop() stack.pop() nodes_seen -= 1 stack.append("#") else: nodes_seen += 1 stack.append(node) return len(stack) == 1 and stack[0] == "#" and nodes_seen >= 1

The time complexity of this solution is O(n), where n is the length of the traversal string, since we iterate through the string once and perform constant-time operations on each character. The space complexity is O(n), since the size of the stack can be at most n/2 + 1.

1