331. Verify Preorder Serialization of a Binary Tree

Description

The problem asks to determine whether a given preorder traversal string represents a valid serialization of a binary tree. The nodes in the tree are represented by integers and nulls, where null nodes are represented by # and the nodes are separated by commas.

A valid serialization must accurately represent a binary tree, with non-null nodes having exactly two children (either null or non-null), and null nodes indicating the absence of a subtree.

Intuition

The idea is to use a balance counter to represent the difference between the number of non-null nodes that expect child nodes and the number of child nodes provided by null nodes or subsequent non-null nodes.

• Each non-null node increases the need for more child nodes (i.e., it adds two child "slots").
• Each null node reduces the need for child nodes (i.e., it consumes one slot).
• By the end of the traversal, all child node "slots" must be fully consumed for the serialization to be valid.

Approach

1. Initial Balance: Start with a balance of 1, as the root node is expected.
2. Traverse through Nodes: - For each node in the preorder string (split by commas): - If it's a null node (#), decrease the balance as it fills one child node slot. - If it's a non-null node, increase the balance by 1 (it contributes two new slots but fills one). - If at any point the balance becomes negative, it means there are too many null nodes, making the serialization invalid.
3. Final Balance Check: After processing all nodes, the balance should be exactly zero, indicating all slots were properly filled.

Complexity

Time Complexity:

• The function splits the input string by commas and iterates over the resulting nodes.
• This gives a time complexity of (O(n)), where (n\) is the length of the preorder string.

Space Complexity:

• The space complexity is (O(n)) due to the storage required for splitting the string into nodes.
• The balance counter and a few other variables occupy constant space, so additional space usage is minimal.

Code

C++

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int balance = 1;
        stringstream ss(preorder);
        string node;

        while (getline(ss, node, ',')) {
            if (balance <= 0) return false;
            if (node == "#") --balance;
            else ++balance;
        }
        return balance == 0;
    }
};

Python

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        balance = 1
        for node in preorder.split(','):
            if balance <= 0:
                return False
            if node == '#':
                balance -= 1
            else:
                balance += 1
        return balance == 0

Java

class Solution {
    public boolean isValidSerialization(String preorder) {
        int balance = 1;
        String[] nodes = preorder.split(",");
        
        for (String node : nodes) {
            if (balance <= 0) return false;
            if (node.equals("#")) balance--;
            else balance++;
        }
        
        return balance == 0;
    }
}

JavaScript

/**
 * @param {string} preorder
 * @return {boolean}
 */
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
}