Leetcode Verify Preorder Serialization of a Binary Tree problem solution

YASH PAL,

In this Leetcode Verify Preorder Serialization of a Binary Tree problem solution, 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.

Leetcode Verify Preorder Serialization of a Binary Tree problem solution

Problem solution in Python.

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        preorderList = preorder.split(',')
        if len(preorderList)%2 != 1:
            return False
        stack = []
        for node in preorderList:
            stack.append(node)
            while len(stack) >= 3 and stack[-2] == stack[-1] == '#' and stack[-3] != '#':
                for i in range(3):
                    stack.pop()
                stack.append('#')
        return len(stack) == 1 and stack[0] == '#'

Problem solution in Java.

public boolean isValidSerialization(String preorder) {

    if(preorder.length()==1 && preorder.charAt(0)=='#'){
        return true;
    }
    
    Deque<Boolean> stackObj = new ArrayDeque<Boolean>();
    
   String[] nodes= preorder.split(",");
    
    for(int i=0;i<nodes.length;i++){
        
        if(nodes[i].equals("#")){
            
            if(stackObj.isEmpty()){
                return false;
            }else{
                
               while(!stackObj.isEmpty() && stackObj.getFirst()){
                stackObj.removeFirst();
               }
                
                if(!stackObj.isEmpty()){
                    stackObj.removeFirst();
                    stackObj.addFirst(true);
                }else if(i+1<nodes.length){
                    return false;
                }
            }
        }else{
            stackObj.addFirst(false);
        }
    }
    
    if(stackObj.isEmpty()){
        return true;
    }
    
    return false;[]
}

Problem solution in C++.

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int internalNode = 0, externalNode = 0;
        char inString[preorder.length() + 1];
        strcpy(inString, preorder.c_str());
        char *nodeValue = strtok(inString, ",");
        while (nodeValue) {
            if (nodeValue[0] == '#') ++externalNode;
            else ++internalNode;
            nodeValue = strtok(NULL, ",");
            if (externalNode == internalNode + 1) {
                if (nodeValue) return false;
                return true;
            }
        }
        return false;
    }
};

Problem solution in C.

char *checkTree(char *start) {
    if (*start == 0) return 0;
    if (*start == '#') return start + 1;
    char *next = start + 1;
    next = checkTree(next);
    if (next == 0) return 0;
    next = checkTree(next);
    if (next == 0) return 0;
    return next;
}

bool isValidSerialization(char * preorder){
    char *c; int i;
    for (c = preorder, i = 0; *c; c++) {
        if (*c == ',') { i++; continue; }
        if (*c != '#') { preorder[i] = 'X'; continue; }
        preorder[i] = '#';
    }
    preorder[i+1] = 0;

    char *end = checkTree(preorder);
    if (end == 0) return false;
    if (*end != 0) return false;
    return true;
}

coding problems solutions