## # 331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order 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 #.

``````     _9_
/   \
3     2
/ \   / \
4   1  #  6
/ \ / \   / \
# # # #   # #
``````

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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

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".

Example 1:

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

Example 2:

``````Input: "1,#"
Output: false
``````

Example 3:

``````Input: "9,#,#,1"
Output: false
``````

### # Solution

Approach 1: observe that in a preorder traversal, two consecutive #s means the previous number is a leaf. Use a stack to 'reduce' all leafs and we should be able to clear out the stack.

Approach 2: an extension to the stack based approach -- the numbers doesn't matter, just count the number of available leaf slots.

Approach 3: (this approach goes TLE) a valid preorder serialization can be broken up to 3 parts: the first item being a number, and two subtrees that are both valid preorder serializations (recursion). Can use a cache or dp to speed things up.

### # Code (Python)

Approach 1:

``````    def isValidSerialization(self, preorder):
stack = []
for node in preorder.split(','):
stack.append(node)
# to 'reduce' leaves: when seeing two consecutive #s on stack, pop both and replace the topmost element on the stack with a single #, essentially replacing a leaf with a null value
while len(stack) >= 3 and stack[-2:] == ['#', '#']:
if stack[-3] == '#': # a leaf can't have children
return False
stack[-3:] = '#'
return stack == ['#']
``````

Approach 2:

``````    def isValidSerialization(self, preorder):
available_slots = 1
for node in preorder.split(','):
if available_slots <= 0:
return False
if node != '#':
available_slots += 1 # the number takes a slot, but increase 2 slots
else:
available_slots -= 1 # the pound takes a slot
return available_slots == 0
``````

Approach 3:

``````    def isValidSerialization(self, preorder):
sequence = preorder.split(',')
cache = {}
return self._is_valid_preorder(sequence, 0, len(sequence) - 1, cache)

def _is_valid_preorder(self, sequence, start, end, cache):
# a leaf node can only be a #, not number
if start == end:
return sequence[start] == '#'
# a root can't be a #
if sequence[start] == '#':
return False
for i in range(start + 1, end):
if (start + 1, i) not in cache:
cache[(start + 1, i)] = self._is_valid_preorder(sequence, start + 1, i, cache)
first_half_valid = cache[(start + 1, i)]
if (i + 1, end) not in cache:
cache[(i + 1, end)] = self._is_valid_preorder(sequence, i + 1, end, cache)
second_half_valid = cache[(i + 1, end)]
if first_half_valid and second_half_valid:
return True
return False
``````

### # Code (C++)

Approach 1:

``````// Stack - O(n) space.
class Solution {
public:
bool isValidSerialization(string preorder) {
stack<string> st;
int tail = 1;
while (tail <= preorder.size())
{
if (tail == preorder.size() || preorder[tail] == ',')
{
if (node == "#")
{
while (!st.empty() && st.top() == "#")
{
st.pop();
if (st.empty())
return false;
st.pop();
}
}
st.push(node);
}
tail++;
}
return (st.size() == 1 && st.top() == "#");
}
};
``````

Approach 2:

``````// O(1) space.
class Solution {
public:
bool isValidSerialization(string preorder) {
int tail = 1;
int open = 1;
while (tail <= preorder.size())
{
if (tail == preorder.size() || preorder[tail] == ',')
{
if (node == "#")
open--;
else
open++;
if (open == 0 && tail < preorder.size())
return false;
}
tail++;
}
return open == 0;
}
};
``````

Approach 3:

``````// Time Limit Exceeded.
class Solution {
public:
bool isValidSerialization(string preorder) {
// Retrive all nodes from the string.
vector<string> nodes;
int tail = 1;
while (tail <= preorder.size())
{
if (tail == preorder.size() || preorder[tail] == ',')
{
nodes.push_back(node);
}
tail++;
}
int n = nodes.size();
bool status[n][n];
for (int i = 0; i < n; ++i)
{
status[i][i] = nodes[i] == "#";
}
for (int len = 2; len <= n; ++len)
{
for (int tail = n-1; tail - len + 1 >= 0; --tail)
{
int head = tail - len + 1;
continue;
for (int i = head + 1; i < tail; ++i)
{