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.
"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 <= 104preorder consist of integers in the range [0, 100] and '#' separated by commas ','.The key idea in #331 Verify Preorder Serialization of a Binary Tree is to validate whether a given preorder traversal string can represent a valid binary tree without actually reconstructing the tree. The serialization uses commas to separate nodes and # to represent null pointers.
A common and efficient strategy is the slot counting approach. Initially, the root provides one available slot. Each node consumes a slot; if the node is non-null, it creates two additional slots for its children. By processing tokens sequentially, you track how slots are filled and created. If slots ever become negative or do not end at zero, the serialization is invalid.
Another approach uses a stack-based reduction. When the pattern node,#,# appears, it represents a completed subtree and can be collapsed into a single #. Repeating this reduction helps verify if the entire structure reduces to a single null marker.
Both methods scan the string once, making them efficient for interview scenarios with O(n) time complexity and O(1)–O(n) space depending on the technique used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Slot Counting (Greedy) | O(n) | O(1) |
| Stack-Based Reduction | O(n) | O(n) |
NeetCode
The idea is to track available slots in the binary tree. Initially, we start with one slot for the root. For each node, we consume a slot. If the node is non-null, it adds two more slots (one for each child). A null node ('#') does not add any slots. The binary tree is valid if, at the end of processing all nodes, all slots are exactly filled (i.e., zero slots remaining).
Time Complexity: O(n), where n is the length of the preorder string, as we are iterating through the nodes once.
Space Complexity: O(1), with no additional data structures used.
1public class Solution {
2 public boolean isValidSerialization(String preorder) {
3 int slots = 1;
4 String[] nodes = preorderThe Java solution utilizes the split function to tokenize the string by commas. The algorithm then follows the same slot accounting logic to validate the serialization.
This approach involves simulating a stack-based tree traversal. The idea is to treat each "open bracket" as requiring nodes and each "close bracket" as completing them. We aim to manage the state of openings and closures using integers, representing how many nodes are expected at any point in the traversal.
Time Complexity: O(n), parsing each node once.
Space Complexity: O(1), with only integer variables used for tracking.
#include <string>
#include <iostream>
using namespace std;
bool isValidSerialization(string preorder) {
int diff = 1;
stringstream ss(preorder);
string node;
while (getline(ss, node, ',')) {
if (--diff < 0) return false;
if (node != "#") diff += 2;
}
return diff == 0;
}
int main() {
string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
cout << (isValidSerialization(preorder) ? "true" : "false");
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The symbol # represents a null node in preorder serialization. Including null markers ensures that the exact structure of the binary tree can be reconstructed or validated, not just the sequence of values.
Yes, this problem or its variations are common in FAANG-style interviews. It tests understanding of tree traversal, serialization concepts, and the ability to validate tree structures without constructing them.
The problem can be solved efficiently without complex data structures using a simple counter for available slots. However, a stack can also be used to reduce completed subtrees when patterns like node,#,# appear during traversal.
The most optimal approach uses the slot counting (indegree–outdegree) technique. Each node consumes a slot, while non-null nodes create two new slots. If slots never become negative and end at zero after processing all nodes, the serialization is valid.
C++ solution employs a stringstream to parse the input string and simulates a stack via differential count adjustments.