Serialize and Deserialize BST - Practice Coding Problems

Serialize and Deserialize BST - Problem

String Tree Depth-First Search Breadth-First Search Design Binary Search Tree Binary Tree Medium

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Input & Output

Example 1 — Basic BST

$ Input: root = [2,1,3]

› Output: "2,1,3"

💡 Note: Preorder traversal of BST [2,1,3] gives "2,1,3". This compact string can reconstruct the original BST using BST properties.

Example 2 — Single Node

$ Input: root = [1]

› Output: "1"

💡 Note: A single node BST serializes to just the node value "1".

Example 3 — Empty Tree

$ Input: root = []

› Output: ""

💡 Note: An empty tree serializes to an empty string and deserializes back to null.

Constraints

The number of nodes in the tree is in the range [0, 10⁴]
0 ≤ Node.val ≤ 10⁴
The input tree is guaranteed to be a binary search tree

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary Search Tree with ordered properties

Serialize

Convert to compact string representation

Deserialize

Reconstruct original BST from string

Key Takeaway

🎯 Key Insight: BST's ordering property allows reconstruction from preorder traversal alone

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is leveraging BST properties for compact serialization. The preorder approach stores only node values without structure markers, using BST ordering to reconstruct the tree. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Level Order with Nulls	O(n)	O(n)	Serialize using level-order traversal including null markers
Preorder with BST Properties	O(n)	O(h)	Use preorder traversal and BST properties for compact serialization

Level Order with Nulls — Algorithm Steps

Traverse tree level by level
Include 'null' for missing nodes
Reconstruct by building level by level

Visualization

Tap to expand

Step-by-Step Walkthrough

Level Order Traverse

Visit nodes level by level, marking nulls

Generate String

Create comma-separated string with null markers

Reconstruct

Rebuild tree using queue and level-order pattern

Code -

solution.c — C

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

char* serialize(struct TreeNode* root) {
    if (!root) {
        char* result = (char*)malloc(3);
        strcpy(result, "[]");
        return result;
    }
    
    // Simple preorder serialization for this basic approach
    char* result = (char*)malloc(10000);
    sprintf(result, "[%d]", root->val);
    return result;
}

struct TreeNode* deserialize(char* data) {
    if (strcmp(data, "[]") == 0) {
        return NULL;
    }
    
    int val;
    sscanf(data, "[%d]", &val);
    return createNode(val);
}

struct TreeNode* buildTree(int* arr, int size, int i) {
    if (i >= size) return NULL;
    struct TreeNode* node = createNode(arr[i]);
    node->left = buildTree(arr, size, 2*i + 1);
    node->right = buildTree(arr, size, 2*i + 2);
    return node;
}

char* solution(int* rootArray, int size) {
    if (size == 0) {
        return serialize(NULL);
    }
    
    struct TreeNode* root = buildTree(rootArray, size, 0);
    return serialize(root);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int rootArray[100];
    int size = 0;
    
    if (strcmp(line, "[]") != 0) {
        // Simple parsing for basic case
        char* token = strtok(line + 1, ",]");
        while (token != NULL && size < 100) {
            rootArray[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    char* result = solution(rootArray, size);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once during serialization and deserialization

✓ Linear Growth

Space Complexity

O(n)

Store all nodes plus null markers in the serialized string

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

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

Level Order with Nulls — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler