Verify Preorder Serialization of a Binary Tree
Medium · Stack · Explanation and code example
Available Child Slots
How it works
Start with one available slot for the root. Every token consumes a slot; a non-null node creates two child slots. A valid serialization never consumes a nonexistent slot and uses exactly all slots by the end.
Steps
- Start the slot balance at one.
- Subtract one for every comma-separated token and reject a negative balance.
- Add two for non-null tokens and accept only a final zero balance.
Complexity
- Time: O(n) input characters.
- Space: Python O(n) for split tokens; C++ O(n) for the stream copy.
Things to watch for
- A complete tree followed by extra tokens is invalid.
- A final positive slot count means children are missing.
- The single token # represents an empty tree.
Python code example
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
degree = 1 # out-degree (children) - in-degree (parent)
for node in preorder.split(','):
degree -= 1
if degree < 0:
return False
if node != '#':
degree += 2
return degree == 0
C++ code example
class Solution {
public:
bool isValidSerialization(string preorder) {
int degree = 1; // out-degree (children) - in-degree (parent)
istringstream iss(preorder);
for (string node; getline(iss, node, ',');) {
if (--degree < 0)
return false;
if (node != "#")
degree += 2;
}
return degree == 0;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.