Last updated on January 9th, 2025 at 02:16 am
Here, we see a Verify Preorder Serialization of a Binary Tree LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Stack
Companies
Level of Question
Medium
Verify Preorder Serialization of a Binary Tree LeetCode Solution
Table of Contents
1. Problem Statement
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.
- For example, it could never contain two consecutive commas, such as “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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Tree Validation using Stack or Slot Counting. The problem involves validating a preorder serialization of a binary tree, which is a unique pattern for tree-related problems.
3. Code Implementation in Different Languages
3.1 Verify Preorder Serialization of a Binary Tree C++
class Solution {
public:
bool isValidSerialization(string preorder) {
stack<char> stk;
bool isNum = false;
preorder.push_back(',');
for(auto c: preorder){
if(c == '#'){
while(!stk.empty() && stk.top() == '#'){
stk.pop();
if(stk.empty() || stk.top() == '#') return false;
stk.pop();
}
stk.push('#');
}else if(c == ','){
if(isNum) stk.push('n');
isNum = false;
}else{
isNum = true;
}
}
return stk.size() == 1 && stk.top() == '#';
}
};
3.2 Verify Preorder Serialization of a Binary Tree Java
class Solution {
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1;
for (String node: nodes) {
if (--diff < 0) return false;
if (!node.equals("#")) diff += 2;
}
return diff == 0;
}
}
3.3 Verify Preorder Serialization of a Binary Tree JavaScript
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
}
3.4 Verify Preorder Serialization of a Binary Tree Python
class Solution(object):
def isValidSerialization(self, preorder):
p = preorder.split(',')
slot = 1
for node in p:
if slot == 0:
return False
if node == '#':
slot -= 1
else:
slot += 1
return slot==0
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(1) |
| Python | O(n) | O(1) |
- All implementations solve the problem using the same core idea: tracking the slot balance to validate the preorder serialization.
- The C++ implementation uses a stack, while the other implementations use a single variable for slot tracking.
- The time complexity is O(n) for all implementations, as they iterate through the input string once.
- The space complexity is O(n) for C++ (due to the stack) and O(1) for Java, JavaScript, and Python (due to the use of a single variable).