# Question

Formatted question description: https://leetcode.ca/all/331.html

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

# Algorithm

1. The number of digits is always one less than #
2. The last one must be #
3. leaf node: number, #, #

If we initialize a counter to 0,

• When a number is encountered, the counter increases by 1,
• When the # sign is encountered, the counter is decreased by 1, Then the counter should still be 0 at the end.

Two examples that return False, #,7,6,9,#,#,# and 7,2,#,2,#,#,#,6,#, then through these two counter examples,

• If the root node is empty, there can be no more nodes behind,
• And there cannot be three consecutive # signs.

So when we add or subtract the counter, if we encounter the # number, and the counter is already 0, and then subtracted to become a negative number, we directly return False, because in the correct sequence, any position i is in [ 0, i] The number of # numbers in the range is not greater than the number of digits.

When the loop is complete, we check whether the counter is 0 and also see whether the last character is # sign.

# Code

• import java.util.Stack;

public class Verify_Preorder_Serialization_of_a_Binary_Tree {

// https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution
public class Solution_noStack {
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1; // if single node tree [root]
for (String node: nodes) {
if (--diff < 0) return false;
if (!node.equals("#")) diff += 2;
}
return diff == 0;
}
}

public class Solution {
public boolean isValidSerialization(String preorder) {
if (preorder == null || preorder.length() == 0) {
return true;
}

String[] nodes = preorder.split(",");
Stack<String> stack = new Stack<>();

for (String node : nodes) {
if (node.equals("#")) {
// after first while loop, current node can be deemed as #
while (!stack.isEmpty() && stack.peek().equals("#")) {
stack.pop(); // pop # in stack
if (stack.isEmpty()) { // should leave a number in stack
return false;
}

stack.pop(); // pop val with left-# and right-#   =>   repalce it with #
}
}

stack.push(node);
}

return stack.size() == 1 && stack.peek().equals("#");
}
}
}

############

class Solution {
public boolean isValidSerialization(String preorder) {
String[] strs = preorder.split(",");
int diff = 1;
for (String s : strs) {
if (--diff < 0) {
return false;
}
if (!s.equals("#")) {
diff += 2;
}
}
return diff == 0;
}
}


• class Solution {
public:
bool isValidSerialization(string preorder) {
istringstream in(preorder);
vector<string> v;
string t = "";
int cnt = 0;
while (getline(in, t, ',')) v.push_back(t);
for (int i = 0; i < v.size() - 1; ++i) {
if (v[i] == "#") {
if (cnt == 0) return false;
--cnt;
} else ++cnt;
}
return cnt == 0 && v.back() == "#";
}
};

class Solution {
public:
bool isValidSerialization(string preorder) {
int capacity = 1;
preorder += ",";
for (int i = 0; i < preorder.size(); ++i) {
if (preorder[i] != ',') continue;
if (--capacity < 0) return false;
if (preorder[i - 1] != '#') capacity += 2;
}
return capacity == 0;
}
};

• '''
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 == "#"


• func isValidSerialization(preorder string) bool {
stk := []string{}
for _, s := range strings.Split(preorder, ",") {
stk = append(stk, s)
for len(stk) >= 3 && stk[len(stk)-1] == "#" && stk[len(stk)-2] == "#" && stk[len(stk)-3] != "#" {
stk = stk[:len(stk)-3]
stk = append(stk, "#")
}
}
return len(stk) == 1 && stk == "#"
}