LeetCode 331: Verify Preorder Serialization of a Binary Tree Solution

Master LeetCode problem 331 (Verify Preorder Serialization of a Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

331. Verify Preorder Serialization of a Binary Tree

Medium

String Stack Tree Binary Tree

Problem Explanation

Explanation

To verify if a given preorder serialization of a binary tree is valid, we can simulate the process of building the tree using a stack. We iterate over the nodes in the preorder serialization and push them onto the stack. Whenever we encounter two consecutive "#" nodes on top of the stack, we pop them along with the parent node and replace them with a single "#". We repeat this process until the stack contains only one element, which should be "#" (representing the root node).

Algorithm:

Split the input preorder string by commas to get individual nodes.
Initialize an empty stack.
Iterate over each node in the preorder list.
- Push the current node onto the stack.
- Check if the top two elements on the stack are "#" and pop them along with the parent node until we cannot perform this operation.
After iterating through all nodes, check if the stack contains only one element "#" which represents a valid binary tree serialization.

Time Complexity: O(n) where n is the number of nodes in the preorder serialization string. Space Complexity: O(n) where n is the number of nodes in the preorder serialization string.

Solution Code

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        
        for (String node : nodes) {
            stack.push(node);
            
            while (stack.size() >= 3 && stack.get(stack.size() - 1).equals("#") && stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {
                stack.pop();
                stack.pop();
                stack.pop();
                stack.push("#");
            }
        }
        
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 331 (Verify Preorder Serialization of a Binary Tree)?

This page provides optimized solutions for LeetCode problem 331 (Verify Preorder Serialization of a Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 331 (Verify Preorder Serialization of a Binary Tree)?

The time complexity for LeetCode 331 (Verify Preorder Serialization of a Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 331 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 331 in Java, C++, or Python.

Back to LeetCode Solutions