🎨Now live: Try our Free AI Image Generation Feature

Description
The problem asks to determine whether a given preorder
traversal string represents a valid serialization of a binary tree. The nodes in the tree are represented by integers and nulls, where null nodes are represented by #
and the nodes are separated by commas.
A valid serialization must accurately represent a binary tree, with non-null nodes having exactly two children (either null or non-null), and null nodes indicating the absence of a subtree.
Intuition
The idea is to use a balance counter to represent the difference between the number of non-null nodes that expect child nodes and the number of child nodes provided by null nodes or subsequent non-null nodes.
- Each non-null node increases the need for more child nodes (i.e., it adds two child "slots").
- Each null node reduces the need for child nodes (i.e., it consumes one slot).
- By the end of the traversal, all child node "slots" must be fully consumed for the serialization to be valid.
Approach
- Initial Balance: Start with a balance of 1, as the root node is expected.
- Traverse through Nodes:
- For each node in the
preorder
string (split by commas): - If it's a null node (#
), decrease the balance as it fills one child node slot. - If it's a non-null node, increase the balance by 1 (it contributes two new slots but fills one). - If at any point the balance becomes negative, it means there are too many null nodes, making the serialization invalid. - Final Balance Check: After processing all nodes, the balance should be exactly zero, indicating all slots were properly filled.
Complexity
Time Complexity:
- The function splits the input string by commas and iterates over the resulting nodes.
- This gives a time complexity of (O(n)), where (n\) is the length of the
preorder
string.
Space Complexity:
- The space complexity is (O(n)) due to the storage required for splitting the string into nodes.
- The balance counter and a few other variables occupy constant space, so additional space usage is minimal.
Code
C++
class Solution {
public:
bool isValidSerialization(string preorder) {
int balance = 1;
stringstream ss(preorder);
string node;
while (getline(ss, node, ',')) {
if (balance <= 0) return false;
if (node == "#") --balance;
else ++balance;
}
return balance == 0;
}
};
Python
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
balance = 1
for node in preorder.split(','):
if balance <= 0:
return False
if node == '#':
balance -= 1
else:
balance += 1
return balance == 0
Java
class Solution {
public boolean isValidSerialization(String preorder) {
int balance = 1;
String[] nodes = preorder.split(",");
for (String node : nodes) {
if (balance <= 0) return false;
if (node.equals("#")) balance--;
else balance++;
}
return balance == 0;
}
}
JavaScript
/**
* @param {string} preorder
* @return {boolean}
*/
var isValidSerialization = function (preorder) {
let balance = 1
for (const node of preorder.split(','))
if (balance > 0)
if (node === '#') --balance
else ++balance
else return false
return balance < 1
}