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.

Note: Note: You are not allowed to reconstruct the tree.

Examples

1. Example 1:
   • Input: "5,2,#,#,3,1,#,#,#"
   • Expected Output: true
   • Justification: The preorder traversal "5,2,#,#,3,1,#,#,#" represents a valid binary tree. It can be visualized as:

    5
   /
  2
   \
    3
    /
   1

2. Example 2:
   • Input: "7,3,1,#,#,4,#,#,8,#,2,#,#"
   • Expected Output: true
   • Justification: The serialization "7,3,1,#,#,4,#,#,8,#,2,#,#" corresponds to a valid binary tree:

    7
   / \
  3   1
     /
    4
     \
      8
       \
        2

3. Example 3:
   • Input: "1,#,#,2"
   • Expected Output: false
   • Justification: The serialization "1,#,#,2" cannot represent a valid binary tree. After the node 1 and its two null children, there should not be any additional nodes left, but 2 appears, which violates the preorder traversal structure.

Try it yourself

Try solving this question here: