Last updated on July 20th, 2024 at 12:05 am

Here, We see Verify Preorder Serialization of a Binary Tree LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Stack

Companies

Google

Level of Question

Medium

Verify Preorder Serialization of a Binary Tree LeetCode Solution

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

1. Verify Preorder Serialization of a Binary Tree LeetCode Solution 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() == '#';
    }
};

2. Verify Preorder Serialization of a Binary Tree LeetCode Solution 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. Verify Preorder Serialization of a Binary Tree Solution 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
}

4. Verify Preorder Serialization of a Binary Tree Solution 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