algoadvance

Leetcode 331. Verify Preorder Serialization of a Binary Tree

Problem Statement

Given a string of comma-separated values, verify whether it represents a correct preorder serialization of a binary tree. A null node is represented by a #.

For example, the string “9,3,4,#,#,1,#,#,2,#,6,#,#” corresponds to the following binary tree:

    9
   / \
  3   2
 / \   \
4   1   6

Each comma-separated value indicates a node, and # represents a null node.

Clarifying Questions

1. Input Constraints: What is the maximum length of the input string?
2. Edge Cases: Should we handle edge cases such as an empty string or purely null node tree?
3. Return Type: Should the function return a boolean value indicating whether the serialization is valid?

Strategy

To solve this problem, we can simulate the process of forming the binary tree using a counter for slots. Each non-null node uses one slot but creates two new slots, whereas a null node uses one slot without creating any new slot.

Steps:

1. Initialize a counter with 1 slot (for the root node).
2. Split the input string by commas to process each node.
3. Iterate through the nodes and:
   • Decrement the counter for each node visited (since it occupies one slot).
   • If the node is not null, increment the counter by 2 (since it provides two new slots for its children).
   • If at any point the counter becomes negative, return false (indicating an invalid serialization).
4. After processing all nodes, ensure the counter is exactly 0.

Edge Cases:

• An empty input string should be handled.
• A single null node is a valid binary tree.

Code

#include <iostream>
#include <sstream>

bool isValidSerialization(std::string preorder) {
    std::istringstream iss(preorder);
    std::string node;
    int slots = 1;
    
    while (std::getline(iss, node, ',')) {
        slots--;  // one slot is taken by the current node

        // if at any point slots are less than 0, the serialization is invalid
        if (slots < 0) {
          return false;
        }

        // non-null node produces two additional slots
        if (node != "#") {
            slots += 2;
        }
    }
    
    // slots should be zero if the serialization is valid
    return slots == 0;
}

int main() {
    std::string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
    std::cout << (isValidSerialization(preorder) ? "Valid" : "Invalid") << std::endl;

    std::string preorder_invalid = "1,#";
    std::cout << (isValidSerialization(preorder_invalid) ? "Valid" : "Invalid") << std::endl;

    return 0;
}

Time Complexity

• Time Complexity: O(n)
  • Splitting the string and iterating through nodes happens linearly with respect to the length of the input string.
• Space Complexity: O(1)
  • Only a few variables (slots, node) are used, and we do not use any additional space proportional to the input size.

This solution efficiently verifies the preorder serialization string of a binary tree with a linear time complexity and constant space complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?