# Verify Preorder Serialization of a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/verify-preorder-serialization-of-a-binary-tree
**Algorithms:** [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
**Data structures:** String, Stack, Tree, Binary Tree
---
## Problem
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 `'#'`.

![](https://assets.glich.co/dsa/verify-preorder-serialization-of-a-binary-tree/image0.jpg) 

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 `','`.

# Approaches
## Stack-based Reduction
This approach uses a stack to iteratively validate the preorder string. The main idea is to treat a `(number, #, #)` sequence as a complete subtree that can be 'reduced' or replaced by a single `'#`' from its parent's perspective. By processing the nodes and performing these reductions, a valid serialization should ultimately simplify to a single `'#`', representing the entire valid tree.
**Time:** O(N), where N is the number of nodes. The string split operation takes O(L) time (L is string length, proportional to N). Each node is pushed onto the stack once. The inner `while` loop might seem to add complexity, but each element is popped at most once, leading to an amortized O(1) time per node. · **Space:** O(N), where N is the number of nodes in the serialization. This is due to storing the split string in an array and the space used by the stack, which in the worst-case (a skewed tree) can hold O(N) elements.
**Pros:** Avoids recursion, which can prevent stack overflow errors on deeply skewed trees.; The logic directly simulates the hierarchical nature of the tree structure.
**Cons:** Requires O(N) extra space for the stack, which can be significant for large inputs.; The logic involving the reduction loop can be slightly more complex to reason about than a direct counting method.
### Explanation
We can simulate the tree validation process using a stack. We iterate through the nodes provided in the preorder string. When we encounter a number, it represents a new subtree root, so we push it onto the stack. When we encounter a null marker (`#`), it signifies the end of a branch. 

A key observation is that a node followed by two null markers (e.g., `4,#,#`) forms a complete leaf node from its parent's point of view. This entire structure can be conceptually replaced by a single `#`. We implement this by checking if the top of our stack is a `#` when we see a new `#`. If so, we pop the existing `#` and its parent number, effectively reducing them. We repeat this until the condition is no longer met. Finally, we push the current `#` onto the stack.

If the preorder string is valid, this process will consume all nodes and leave a single `#` on the stack at the end. Any other final state of the stack indicates an invalid serialization.

```java
import java.util.Stack;

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        
        for (String node : nodes) {
            if (node.equals("#")) {
                // Reduce "number,#,#" to "#"
                while (!stack.isEmpty() && stack.peek().equals("#")) {
                    stack.pop(); // Pop the first '#'
                    // After a '#', there must be a number to form a pair
                    if (stack.isEmpty() || stack.peek().equals("#")) {
                        return false; 
                    }
                    stack.pop(); // Pop the number
                }
                stack.push("#");
            } else {
                stack.push(node);
            }
        }
        
        // A valid serialization will be reduced to a single '#'
        return stack.size() == 1 && stack.peek().equals("#");
    }
}
```
### Algorithm
- Split the input `preorder` string by commas to get an array of `nodes`.
- Initialize an empty `stack` of strings.
- Iterate through each `node` in the `nodes` array:
  - If the `node` is a number, push it onto the `stack`.
  - If the `node` is `'#`':
    - Repeatedly check if the top of the stack is also `'#`'. This signifies a `number, #, #` pattern.
    - If it is, pop the `'#`' and the preceding number from the stack. This 'reduces' the subtree to a single conceptual `'#`'.
    - After the reduction loop, push the current `'#`' onto the stack.
- After iterating through all nodes, a valid serialization will result in the stack containing exactly one element: `'#`'.
- If the final stack state is `['#']`, return `true`; otherwise, return `false`.

## Degree Counting (Slot-based)
This highly efficient approach relies on counting the 'in-degree' and 'out-degree' of nodes. A non-null node has an in-degree of 1 and an out-degree of 2. A null node (`#`) has an in-degree of 1 and an out-degree of 0. For a valid tree, the sum of out-degrees must equal the sum of in-degrees for all nodes except the root.

We can simplify this by maintaining a running count of available 'slots'. We start with one slot for the root. Each node consumes one slot. A non-null node adds two new slots. A valid serialization will end with exactly zero available slots.
**Time:** O(N), where N is the number of nodes. We perform a single pass over the nodes after the initial split. The split operation itself is proportional to the length of the string, which is O(N). · **Space:** O(N) for the given implementation due to `preorder.split(",")`. This can be easily optimized to O(1) by creating a simple parser that iterates through the input string and identifies nodes without storing them in an intermediate array.
**Pros:** Extremely efficient with O(N) time complexity and can be optimized to O(1) space.; The logic is simple and robust, based on a fundamental property of trees.; It's a single-pass solution without complex data structures like stacks or recursion.
**Cons:** The provided code snippet uses `String.split()`, which requires O(N) space. To achieve true O(1) space, a manual parser for the string is needed, which adds minor implementation complexity.
### Explanation
The core idea is to treat the tree construction as a balance of supply and demand for node slots. We start with a demand for one node (the root), which we can represent as `slots = 1`.

We then iterate through the preorder sequence. Each element in the sequence, whether it's a number or a `'#`', fills one available slot. So, for each element, we decrement our `slots` counter. If the counter ever drops below zero, it means we have more nodes than available slots, indicating an invalid sequence.

If the element we process is a number (a non-null node), it also supplies two new slots for its left and right children. Therefore, after decrementing `slots` for the node itself, we increment `slots` by 2.

After iterating through the entire sequence, a valid tree serialization must have a perfect balance, meaning `slots` should be exactly 0. If it's positive, it means there are unfilled slots; if it were negative, we would have already returned false.

This method is extremely fast and can be optimized to use constant space by parsing the input string directly instead of splitting it into an array first.

```java
class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int slots = 1; // Start with one slot for the root

        for (String node : nodes) {
            // Each node consumes one slot
            slots--;

            // If we run out of slots before processing all nodes, it's invalid
            if (slots < 0) {
                return false;
            }

            // A non-null node provides two new slots for its children
            if (!node.equals("#")) {
                slots += 2;
            }
        }

        // At the end, all slots must be filled
        return slots == 0;
    }
}
```
### Algorithm
- First, split the `preorder` string into an array of `nodes`.
- Initialize a counter variable, `slots`, to `1`. This represents the single available slot for the root of the tree.
- Iterate through each `node` in the `nodes` array:
  - Decrement `slots` by 1, as each node (whether null or not) consumes one slot.
  - If `slots` becomes negative at any point, it means we are trying to add a node where no parent slot is available. This is an invalid structure, so return `false` immediately.
  - If the current `node` is not a `'#`', it is a non-null node. A non-null node provides two new slots for its children, so increment `slots` by 2.
- After the loop has finished, a valid serialization must have used up all available slots perfectly. Therefore, check if `slots` is exactly `0`. If it is, return `true`; otherwise, return `false`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  bool isValidSerialization(string preorder) {
    vector<string> stk;
    stringstream ss(preorder);
    string s;
    while (getline(ss, s, ',')) {
      stk.push_back(s);
      while (stk.size() >= 3 && stk[stk.size() - 1] == "#" &&
             stk[stk.size() - 2] == "#" && stk[stk.size() - 3] != "#") {
        stk.pop_back();
        stk.pop_back();
        stk.pop_back();
        stk.push_back("#");
      }
    }
    return stk.size() == 1 && stk[0] == "#";
  }
};

```

### Python

```python
''' In this solution, we split the input string by comma to get a list of nodes. We then initialize the indegree counter to 1 for the root node, since the root has no incoming edges. We then loop through the nodes and for each node, we decrease the indegree counter by 1. If the indegree counter becomes negative, it means that there are more incoming edges than expected, and the tree is invalid. In this case, we return False. If the current node is not null (i.e., not '#'), we increase the indegree counter by 2 for its two children. This is because every non-null node has two children in a binary tree. Finally, we return True if the final indegree counter is 0, meaning that all incoming edges have been accounted for. ''' class Solution : def isValidSerialization ( self , preorder : str ) -> bool : # Split the string by comma to get the list of nodes nodes = preorder . split ( ',' ) # since the root has no incoming edges indegree = 1 for node in nodes : # Decrease the indegree for the current node indegree -= 1 # If the indegree is negative, return False because the tree is invalid if indegree < 0 : return False # If the current node is not null, increase the indegree by 2 for its children if node != '#' : indegree += 2 # Return True if the final indegree is 0 return indegree == 0 ############ class Solution : def isValidSerialization ( self , preorder : str ) -> bool : if not preorder : return True nodes = preorder . split ( "," ) stack = [] for node in nodes : if node == "#" : # after first while loop, current node can be deemed as # while stack and stack [ - 1 ] == "#" : stack . pop () # pop # in stack if not stack : # should leave a number in stack return False stack . pop () # pop val with left-# and right-# => repalce it with # stack . append ( node ) return len ( stack ) == 1 and stack [ 0 ] == "#" ############ class Solution : def isValidSerialization ( self , preorder : str ) -> bool : stk = [] for c in preorder . split ( "," ): stk . append ( c ) while len ( stk ) > 2 and stk [ - 1 ] == stk [ - 2 ] == "#" and stk [ - 3 ] != "#" : stk = stk [: - 3 ] stk . append ( "#" ) return len ( stk ) == 1 and stk [ 0 ] == "#"
```