**Solution with discussion**https://discuss.leetcode.com/topic/80426/python-solution-with-detailed-explanation

**Verify Preorder Serialization of a Binary Tree** https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

**Stack Simulation**

- The algorithm idea can be summarized with the picture in this post: http://www.programcreek.com/2015/01/leetcode-verify-preorder-serialization-of-a-binary-tree-java/
- Same idea: https://discuss.leetcode.com/topic/35977/simple-python-solution-using-stack-with-explanation/2
- The code can be tricky to get absolutely correct. Notice all the conditions.
- Time complexity is O(N) and space complexity is O(N).
- Note - "#" will be a null tree and must return True.

```
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
st = []
for x in preorder.split(","):
st.append(x)
while len(st) > 2 and st[-1] == "#" and st[-2] == "#":
st.pop()
st.pop()
if st.pop() == "#":
return False
st.append("#")
return bool(len(st)==1 and st[-1]=="#")
```

**In-Degree and Out-Degree Concept**

- In a binary tree, we can generalize the following:
- Leaf node is "#". Leaf node has in-degree 1 and out-degree = 0
- Internal node (non leaf but not root) will have in-degree 1 (just one parent) and out-degree = 2
- Root node has 0 in-degree and 2 out-degree.
- Now the invariant is that after looking at a node and incrementing in-degree, the invariant i.e, in-degree <= out_degree must be true.That is because all the potential in-degree count in the tree are solely contributed by the out-degree by the previous nodes.
- The position of that check is very critical.

```
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
preorder = preorder.split(",")
in_degree, out_degree = 0, 0
for idx, x in enumerate(preorder):
in_degree = in_degree + 1 if idx != 0 else in_degree
if in_degree > out_degree:
return False
out_degree = out_degree+2 if x != "#" else out_degree
return in_degree == out_degree
```