# Python solution with detailed explanation

• Solution with discussionhttps://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

``````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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.