{x}
blog image

Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'.

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid.

  • For example, it could never contain two consecutive commas, such as "1,,3".

Note: You are not allowed to reconstruct the tree.

 

Example 1:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Example 2:

Input: preorder = "1,#"
Output: false

Example 3:

Input: preorder = "9,#,#,1"
Output: false

 

Constraints:

  • 1 <= preorder.length <= 104
  • preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

Solution Explanation: Verify Preorder Serialization of a Binary Tree

This problem asks to determine if a given comma-separated string represents a valid preorder serialization of a binary tree. We can't reconstruct the tree; we need to analyze the string directly. The key insight is that a node needs two slots for its children (left and right). Null nodes are represented by '#'.

Approach:

The efficient solution uses a stack to track the nodes. We process the preorder string one node at a time. Each node consumes two slots (for its children) unless it's a null node ('#').

  1. Initialization: Start with an empty stack.

  2. Iteration: Process each node (comma-separated value) in the preorder string:

    • Push the node onto the stack.
    • Check if the stack has enough elements (at least 3) to form a complete node-child structure:
      • If the last three elements are node, "#", "#" (where node is not '#'), then it represents a complete node with two null children. This means the node has been completely processed. Remove these three elements and push "#" back onto the stack, effectively representing that the current node has been completed and only its parent's space remains.
    • This compression simulates the process of visiting a node and its children.

  3. Validation: After processing the entire string:

    • If the stack contains only one element, and that element is "#", then the serialization is valid. This signifies that all nodes have been successfully "consumed".

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the preorder string. We iterate through the string once, and the stack operations take constant time per node.
  • Space Complexity: O(n) in the worst case, because the stack's size could grow to n (e.g., a completely skewed tree).

Code Implementation (Python):

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        stack = []
        for node in preorder.split(','):
            stack.append(node)
            while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':
                stack.pop()
                stack.pop()
                stack.pop()
                stack.append('#')  # Simulate consuming the node and its children
        return len(stack) == 1 and stack[0] == '#'

Code Implementation (Java):

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public boolean isValidSerialization(String preorder) {
        List<String> stack = new ArrayList<>();
        for (String node : preorder.split(",")) {
            stack.add(node);
            while (stack.size() >= 3 && stack.get(stack.size() - 1).equals("#") &&
                    stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {
                stack.remove(stack.size() - 1);
                stack.remove(stack.size() - 1);
                stack.remove(stack.size() - 1);
                stack.add("#");
            }
        }
        return stack.size() == 1 && stack.get(0).equals("#");
    }
}

The other language implementations (C++, Go, TypeScript) follow a very similar pattern, adapting the stack operations to the specific language's syntax. The core logic remains identical.