Verify Preorder Serialization of a Binary Tree

Verify Preorder Serialization of a Binary Tree - Problem

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 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.

Note: You are not allowed to reconstruct the tree.

Input & Output

Example 1 — Valid Serialization

$ Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"

› Output: true

💡 Note: This represents a valid binary tree where root=9 has children 3 and 2. Node 3 has children 4 and 1. All leaves properly terminated with '#'.

Example 2 — Invalid Serialization

$ Input: preorder = "1,#"

› Output: false

💡 Note: A non-null node must have exactly two children. Node 1 has only one child ('#'), missing the second child.

Example 3 — Single Null Node

$ Input: preorder = "#"

› Output: true

💡 Note: A single null node is a valid empty tree serialization.

Constraints

1 ≤ preorder.length ≤ 10⁴
preorder consist of integers and '#' separated by commas ','.

Visualization

Tap to expand

Understanding the Visualization

Input

Comma-separated preorder traversal with '#' for null nodes

Validation

Check if it represents a valid binary tree structure

Output

Return true if valid, false otherwise

Key Takeaway

🎯 Key Insight: Track slot balance - each node uses 1 slot, non-null nodes create 2 slots

Asked in

G Google 42 a Amazon 38 M Microsoft 25 f Facebook 22

The key insight is that each node consumes exactly 1 slot but non-null nodes create 2 new slots. By tracking this balance with a simple counter, we can validate the serialization in O(n) time and O(1) space without reconstructing the tree.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Tree Construction	O(n)	O(n)	Try to build the actual tree and check if all tokens are consumed
Stack-Based Validation	O(n)	O(h)	Use stack to track incomplete nodes and their remaining children
Degree Counting	O(n)	O(1)	Track the balance between available slots and nodes using a simple counter

Recursive Tree Construction — Algorithm Steps

Split preorder string by commas
Use recursive function to build tree
Check if all tokens consumed and tree is valid

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Tokens

Split string into individual tokens

Build Recursively

For each non-null node, expect two children

Validate

Check if all tokens used and tree is complete

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char tokens[10000][20];
int tokenCount;
int index_global;

bool buildTree() {
    if (index_global >= tokenCount) {
        return false;
    }
    
    char* token = tokens[index_global++];
    
    if (strcmp(token, "#") == 0) {
        return true;
    }
    
    // Non-null node must have two children
    bool leftValid = buildTree();
    bool rightValid = buildTree();
    
    return leftValid && rightValid;
}

bool solution(char* preorder) {
    tokenCount = 0;
    index_global = 0;
    
    // Parse tokens
    char* token = strtok(preorder, ",");
    while (token != NULL) {
        strcpy(tokens[tokenCount++], token);
        token = strtok(NULL, ",");
    }
    
    bool valid = buildTree();
    return valid && index_global == tokenCount;
}

int main() {
    char preorder[10000];
    fgets(preorder, sizeof(preorder), stdin);
    preorder[strcspn(preorder, "\n")] = 0;
    
    bool result = solution(preorder);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each token is processed exactly once during tree construction

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth can be O(n) in worst case plus space for tokens array

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Tree Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler