Serialize and Deserialize Binary Tree

🎯

Serialize and Deserialize Binary Tree

hardTREEFacebookAmazonGoogle

Imagine you want to save a complex family tree to a file and later reconstruct it exactly as it was. How do you convert the tree into a string and then back into the original tree structure?

💡 This problem involves converting a binary tree into a string format and then reconstructing the tree from that string. Beginners often struggle because trees are recursive structures and encoding null children properly is crucial to avoid ambiguity.

📋

Problem Statement

Design an algorithm to serialize a binary tree into a string and deserialize the string back to the original binary tree structure. Serialization converts the tree into a string representation that can be stored or transmitted, and deserialization reconstructs the tree from that string. The tree nodes contain integer values. Implement two functions: serialize(root) which returns a string, and deserialize(data) which returns the root of the tree.

The number of nodes in the tree is in the range [0, 10^5].Node values are integers and can be negative or positive.The serialization and deserialization must be lossless and efficient.

💡

Example

Input"root = [1,2,3,null,null,4,5]"

Output[1,2,3,null,null,4,5]

The tree is serialized using preorder traversal with null markers. Deserializing the string reconstructs the exact same tree.

• Empty tree → should serialize to an empty string or a special marker and deserialize to null
• Tree with only left children → serialization must correctly represent null right children
• Tree with only right children → serialization must correctly represent null left children
• Tree with negative and zero values → serialization must handle all integer values correctly

⚠️

Common Mistakes

Not including null markers in serialization

Deserialization produces incorrect or incomplete tree structure

✅ Always add explicit null markers for missing children

Using incorrect delimiter or inconsistent splitting

Deserialization fails or throws errors due to wrong parsing

✅ Use a consistent delimiter (e.g., comma) and split accordingly

Not handling empty tree (null root) properly

Code crashes or returns wrong result for empty input

✅ Check for null root and return appropriate serialization (e.g., 'X' or empty string)

Mixing up left and right children during deserialization

Tree structure is incorrect, children swapped or missing

✅ Follow the exact traversal order and assign children in correct sequence

Using recursion without considering stack overflow for deep trees

Runtime error due to exceeding call stack limit

✅ Implement iterative solutions using explicit stacks if needed

🧠

Brute Force (Preorder Traversal with Null Markers)

💡 This approach uses a straightforward preorder traversal and explicitly records null children. It is the foundation for understanding serialization and deserialization, though it can be inefficient for very large trees.

Intuition

Traverse the tree in preorder and convert each node to a string. For null children, add a special marker like 'X'. Join all values with a delimiter. To deserialize, read values in order and rebuild the tree recursively.

Algorithm

1. Serialize: Perform a preorder traversal of the tree.
2. For each node, append its value to a list; for null nodes, append a special marker like 'X'.
3. Join the list into a string with a delimiter (e.g., comma).
4. Deserialize: Split the string by the delimiter to get a list of values.
5. Use a recursive helper that reads values in order, creating nodes or returning null for 'X'.

💡 The main challenge is to keep track of the position in the serialized list during deserialization and to handle null nodes explicitly.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        def dfs(node):
            if not node:
                vals.append('X')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        vals = []
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        def dfs():
            val = next(vals)
            if val == 'X':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        vals = iter(data.split(','))
        return dfs()

# Example usage:
# codec = Codec()
# tree_str = codec.serialize(root)
# root = codec.deserialize(tree_str)

Line Notes

class TreeNode:Defines the tree node structure with value and left/right children

def dfs(node):Defines recursive helper to traverse nodes preorder

if not node:Base case: null node represented by 'X'

vals.append('X')Mark null children explicitly to preserve structure

vals.append(str(node.val))Record current node's value as string

dfs(node.left)Recursively serialize left subtree

dfs(node.right)Recursively serialize right subtree

vals = []Initialize list to collect serialized values

return ','.join(vals)Join all values into a single string for output

vals = iter(data.split(','))Create iterator over serialized values for deserialization

val = next(vals)Get next value to reconstruct node or null

if val == 'X':Detect null marker to return None

node = TreeNode(int(val))Create new tree node from integer value

node.left = dfs()Recursively build left subtree

node.right = dfs()Recursively build right subtree

import java.util.*;

public class Codec {
    private static final String NULL = "X";
    private static final String SEP = ",";

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP);
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(SEP)));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals(NULL)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(nodes);
        node.right = deserializeHelper(nodes);
        return node;
    }

    // TreeNode class definition
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // Example usage:
    // Codec codec = new Codec();
    // String serialized = codec.serialize(root);
    // TreeNode root = codec.deserialize(serialized);

Line Notes

private static final String NULL = "X";Defines a constant for null node marker

private static final String SEP = ",";Defines delimiter for serialization

serializeHelper(TreeNode node, StringBuilder sb)Recursive preorder traversal to build string

if (node == null)Base case: append null marker and return

sb.append(node.val).append(SEP);Append current node value and separator

serializeHelper(node.left, sb);Serialize left subtree recursively

serializeHelper(node.right, sb);Serialize right subtree recursively

Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(SEP)));Split serialized string into queue for deserialization

String val = nodes.poll();Get next value from queue to reconstruct node

if (val.equals(NULL)) return null;Return null if marker found

TreeNode node = new TreeNode(Integer.parseInt(val));Create node from integer value

node.left = deserializeHelper(nodes);Recursively build left subtree

node.right = deserializeHelper(nodes);Recursively build right subtree

#include <iostream>
#include <string>
#include <sstream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
    string serialize(TreeNode* root) {
        ostringstream out;
        serializeHelper(root, out);
        return out.str();
    }

    TreeNode* deserialize(const string& data) {
        istringstream in(data);
        queue<string> nodes;
        string val;
        while (getline(in, val, ',')) {
            nodes.push(val);
        }
        return deserializeHelper(nodes);
    }

private:
    void serializeHelper(TreeNode* node, ostringstream& out) {
        if (!node) {
            out << "X,";
            return;
        }
        out << node->val << ',';
        serializeHelper(node->left, out);
        serializeHelper(node->right, out);
    }

    TreeNode* deserializeHelper(queue<string>& nodes) {
        string val = nodes.front();
        nodes.pop();
        if (val == "X") return nullptr;
        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserializeHelper(nodes);
        node->right = deserializeHelper(nodes);
        return node;
    }
};

// Example usage:
// Codec codec;
// string serialized = codec.serialize(root);
// TreeNode* root = codec.deserialize(serialized);

Line Notes

struct TreeNode {Defines tree node structure with value and pointers to children

void serializeHelper(TreeNode* node, ostringstream& out)Recursive helper to write preorder traversal to stream

if (!node)Base case: write null marker 'X,'

out << node->val << ',';Write current node value followed by comma

serializeHelper(node->left, out);Serialize left subtree recursively

serializeHelper(node->right, out);Serialize right subtree recursively

queue<string> nodes;Queue to hold split serialized values for deserialization

while (getline(in, val, ','))Split input string by commas into queue

string val = nodes.front();Get next value to reconstruct node

if (val == "X") return nullptr;Return null for marker

TreeNode* node = new TreeNode(stoi(val));Create new node from string integer

node->left = deserializeHelper(nodes);Recursively build left subtree

node->right = deserializeHelper(nodes);Recursively build right subtree

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Codec {
    serialize(root) {
        const vals = [];
        function dfs(node) {
            if (!node) {
                vals.push('X');
                return;
            }
            vals.push(node.val.toString());
            dfs(node.left);
            dfs(node.right);
        }
        dfs(root);
        return vals.join(',');
    }

    deserialize(data) {
        const vals = data.split(',');
        let index = 0;
        function dfs() {
            if (vals[index] === 'X') {
                index++;
                return null;
            }
            const node = new TreeNode(parseInt(vals[index++]));
            node.left = dfs();
            node.right = dfs();
            return node;
        }
        return dfs();
    }
}

// Example usage:
// const codec = new Codec();
// const serialized = codec.serialize(root);
// const root = codec.deserialize(serialized);

Line Notes

class TreeNode {Defines tree node class with value and left/right children

function dfs(node) {Recursive helper for preorder traversal serialization

if (!node) {Base case: push 'X' to mark null nodes

vals.push('X');Mark null nodes explicitly

vals.push(node.val.toString());Add current node's value as string

dfs(node.left);Serialize left subtree recursively

dfs(node.right);Serialize right subtree recursively

return vals.join(',');Join all values with commas to form serialized string

const vals = data.split(',');Split serialized string into array for deserialization

let index = 0;Index to track current position in array during deserialization

if (vals[index] === 'X') {Detect null marker and return null

const node = new TreeNode(parseInt(vals[index++]));Create node from integer value and advance index

node.left = dfs();Recursively build left subtree

node.right = dfs();Recursively build right subtree

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once during serialization and deserialization. The serialized string stores all nodes and null markers, so space is proportional to n.

💡 For a tree with 20 nodes, about 60 operations occur (each node plus null children), which is efficient enough for typical interview constraints.

Interview Verdict: Accepted

This approach is accepted and commonly used in interviews because it clearly demonstrates understanding of tree traversal and recursion.

🧠

Iterative Serialization and Deserialization Using Stack

💡 This approach avoids recursion by using an explicit stack to perform preorder traversal for serialization and a stack-based method for deserialization. It helps understand iterative tree traversal and can prevent stack overflow on very deep trees.

Intuition

Use a stack to simulate preorder traversal. Push nodes and record values or null markers. For deserialization, use a stack to reconstruct the tree iteratively by tracking nodes and their children.

Algorithm

1. Serialization: Use a stack to traverse the tree preorder.
2. Pop node from stack, append its value or 'X' if null.
3. Push right then left child to stack to maintain preorder order.
4. Deserialization: Use a queue of values from serialized string.
5. Iteratively reconstruct tree nodes using a stack to track parents and assign children.

💡 The main difficulty is managing the stack correctly to maintain preorder order and reconstruct the tree without recursion.

</>

Code

class Codec:
    def serialize(self, root):
        if not root:
            return 'X'
        stack = [root]
        vals = []
        while stack:
            node = stack.pop()
            if node:
                vals.append(str(node.val))
                stack.append(node.right)
                stack.append(node.left)
            else:
                vals.append('X')
        return ','.join(vals)

    def deserialize(self, data):
        vals = data.split(',')
        if vals[0] == 'X':
            return None
        root = TreeNode(int(vals[0]))
        stack = [(root, 0)]  # node and child index (0=left,1=right)
        i = 1
        while stack:
            node, child_idx = stack[-1]
            if i >= len(vals):
                break
            val = vals[i]
            i += 1
            if val != 'X':
                child = TreeNode(int(val))
                if child_idx == 0:
                    node.left = child
                else:
                    node.right = child
                stack[-1] = (node, child_idx + 1)
                stack.append((child, 0))
            else:
                if child_idx == 0:
                    node.left = None
                    stack[-1] = (node, 1)
                else:
                    node.right = None
                    stack.pop()
        return root

# Example usage:
# codec = Codec()
# s = codec.serialize(root)
# root = codec.deserialize(s)

Line Notes

if not root:Handle empty tree edge case immediately

stack = [root]Initialize stack with root for iterative traversal

node = stack.pop()Process current node from stack

if node:If node exists, record value and push children

stack.append(node.right)Push right child first to process left child next

stack.append(node.left)Push left child to stack

vals.append('X')Mark null nodes explicitly

vals = data.split(',')Split serialized string for deserialization

stack = [(root, 0)]Stack holds nodes and which child to assign next

if val != 'X':Create child node if not null marker

stack[-1] = (node, child_idx + 1)Update child index after assigning a child

stack.pop()Pop node when both children assigned

import java.util.*;

public class Codec {
    private static final String NULL = "X";
    private static final String SEP = ",";

    public String serialize(TreeNode root) {
        if (root == null) return NULL;
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) {
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(node.val).append(SEP);
            stack.push(node.right);
            stack.push(node.left);
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals(NULL)) return null;
        String[] vals = data.split(SEP);
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
        stack.push(new Pair<>(root, 0));
        int i = 1;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> top = stack.peek();
            TreeNode node = top.getKey();
            int childIdx = top.getValue();
            if (i >= vals.length) break;
            String val = vals[i++];
            if (!val.equals(NULL)) {
                TreeNode child = new TreeNode(Integer.parseInt(val));
                if (childIdx == 0) node.left = child;
                else node.right = child;
                stack.pop();
                stack.push(new Pair<>(node, childIdx + 1));
                stack.push(new Pair<>(child, 0));
            } else {
                if (childIdx == 0) {
                    node.left = null;
                    stack.pop();
                    stack.push(new Pair<>(node, 1));
                } else {
                    node.right = null;
                    stack.pop();
                }
            }
        }
        return root;
    }

    // TreeNode and Pair classes
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public static class Pair<K,V> {
        private K key;
        private V value;
        public Pair(K key, V value) { this.key = key; this.value = value; }
        public K getKey() { return key; }
        public V getValue() { return value; }
        public void setValue(V value) { this.value = value; }
    }

    // Example usage:
    // Codec codec = new Codec();
    // String s = codec.serialize(root);
    // TreeNode root = codec.deserialize(s);
}

Line Notes

if (root == null) return NULL;Handle empty tree quickly

Deque<TreeNode> stack = new ArrayDeque<>();Use stack for iterative preorder traversal

stack.push(root);Initialize stack with root node

TreeNode node = stack.pop();Process current node from stack

if (node == null)If node is null, append null marker

sb.append(NULL).append(SEP);Append null marker for missing nodes

sb.append(node.val).append(SEP);Append current node value and separator

stack.push(node.right);Push right child first to process left child next

stack.push(node.left);Push left child to stack

String[] vals = data.split(SEP);Split serialized string for deserialization

Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();Stack holds nodes and child index to assign

if (!val.equals(NULL)) {Create child node if not null marker

stack.pop(); stack.push(new Pair<>(node, childIdx + 1));Update child index after assigning a child

stack.push(new Pair<>(child, 0));Push new child node to stack for further assignment

stack.pop();Pop node when both children assigned

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "X";
        stack<TreeNode*> stk;
        stk.push(root);
        string res;
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            if (!node) {
                res += "X,";
                continue;
            }
            res += to_string(node->val) + ",";
            stk.push(node->right);
            stk.push(node->left);
        }
        return res;
    }

    TreeNode* deserialize(const string& data) {
        if (data == "X") return nullptr;
        istringstream in(data);
        string val;
        vector<string> vals;
        while (getline(in, val, ',')) {
            vals.push_back(val);
        }
        TreeNode* root = new TreeNode(stoi(vals[0]));
        stack<pair<TreeNode*, int>> stk;
        stk.push({root, 0});
        int i = 1;
        while (!stk.empty()) {
            auto& [node, childIdx] = stk.top();
            if (i >= (int)vals.size()) break;
            val = vals[i++];
            if (val != "X") {
                TreeNode* child = new TreeNode(stoi(val));
                if (childIdx == 0) node->left = child;
                else node->right = child;
                stk.top().second++;
                stk.push({child, 0});
            } else {
                if (childIdx == 0) {
                    node->left = nullptr;
                    stk.top().second++;
                } else {
                    node->right = nullptr;
                    stk.pop();
                }
            }
        }
        return root;
    }
};

// Example usage:
// Codec codec;
// string s = codec.serialize(root);
// TreeNode* root = codec.deserialize(s);

Line Notes

if (!root) return "X";Handle empty tree edge case

stack<TreeNode*> stk;Stack for iterative preorder traversal

stk.push(root);Initialize stack with root node

TreeNode* node = stk.top();Process current node from stack

stk.pop();Pop node when both children assigned

if (!node)If node is null, append null marker

res += "X,";Append null marker for missing nodes

res += to_string(node->val) + ",";Append current node value and comma

stk.push(node->right);Push right child first to process left child next

stk.push(node->left);Push left child to stack

vector<string> vals;Store split serialized values for deserialization

stack<pair<TreeNode*, int>> stk;Stack holds nodes and child index to assign

if (val != "X") {Create child node if not null marker

stk.top().second++;Increment child index after assigning a child

stk.push({child, 0});Push new child node to stack for further assignment

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Codec {
    serialize(root) {
        if (!root) return 'X';
        const stack = [root];
        const vals = [];
        while (stack.length > 0) {
            const node = stack.pop();
            if (node === null) {
                vals.push('X');
                continue;
            }
            vals.push(node.val.toString());
            stack.push(node.right);
            stack.push(node.left);
        }
        return vals.join(',');
    }

    deserialize(data) {
        if (data === 'X') return null;
        const vals = data.split(',');
        const root = new TreeNode(parseInt(vals[0]));
        const stack = [{node: root, childIdx: 0}];
        let i = 1;
        while (stack.length > 0) {
            const top = stack[stack.length - 1];
            if (i >= vals.length) break;
            const val = vals[i++];
            if (val !== 'X') {
                const child = new TreeNode(parseInt(val));
                if (top.childIdx === 0) top.node.left = child;
                else top.node.right = child;
                top.childIdx++;
                stack.push({node: child, childIdx: 0});
            } else {
                if (top.childIdx === 0) {
                    top.node.left = null;
                    top.childIdx++;
                } else {
                    top.node.right = null;
                    stack.pop();
                }
            }
        }
        return root;
    }
}

// Example usage:
// const codec = new Codec();
// const s = codec.serialize(root);
// const root = codec.deserialize(s);

Line Notes

if (!root) return 'X';Handle empty tree edge case

const stack = [root];Initialize stack for iterative preorder traversal

const node = stack.pop();Process current node from stack

if (node === null)If node is null, append null marker

vals.push('X');Mark null nodes explicitly

vals.push(node.val.toString());Add current node's value as string

stack.push(node.right);Push right child first to process left child next

stack.push(node.left);Push left child to stack

const vals = data.split(',');Split serialized string for deserialization

const stack = [{node: root, childIdx: 0}];Stack holds nodes and which child to assign next

if (val !== 'X') {Create child node if not null marker

top.childIdx++;Increment child index after assigning a child

stack.push({node: child, childIdx: 0});Push new child node to stack for further assignment

stack.pop();Pop node when both children assigned

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is processed once during serialization and deserialization. The stack and output string scale linearly with the number of nodes.

💡 For 20 nodes, this means roughly 60 operations, similar to recursive approach but avoids call stack overhead.

Interview Verdict: Accepted

This iterative approach is accepted and useful when recursion depth is a concern or interviewer requests iterative solutions.

🧠

Optimized Serialization Using Level Order Traversal (BFS)

💡 This approach serializes the tree using breadth-first search (level order) and includes null markers. It can be easier to understand for some and matches the common array representation of trees.

Intuition

Traverse the tree level by level using a queue. Append node values or null markers. For deserialization, reconstruct the tree by reading values level-wise and assigning children accordingly.

Algorithm

1. Serialize: Use a queue to perform level order traversal.
2. Append node values or 'X' for nulls to a list.
3. Trim trailing null markers to reduce string size.
4. Deserialize: Split string into values.
5. Use a queue to assign children level by level.

💡 The challenge is to handle null children properly and avoid infinite loops by trimming trailing nulls.

</>

Code

from collections import deque

class Codec:
    def serialize(self, root):
        if not root:
            return ''
        queue = deque([root])
        vals = []
        while queue:
            node = queue.popleft()
            if node:
                vals.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                vals.append('X')
        # Remove trailing 'X's
        while vals and vals[-1] == 'X':
            vals.pop()
        return ','.join(vals)

    def deserialize(self, data):
        if not data:
            return None
        vals = data.split(',')
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if i < len(vals):
                if vals[i] != 'X':
                    node.left = TreeNode(int(vals[i]))
                    queue.append(node.left)
                i += 1
            if i < len(vals):
                if vals[i] != 'X':
                    node.right = TreeNode(int(vals[i]))
                    queue.append(node.right)
                i += 1
        return root

# Example usage:
# codec = Codec()
# s = codec.serialize(root)
# root = codec.deserialize(s)

Line Notes

from collections import dequeImport deque for efficient queue operations

if not root:Handle empty tree by returning empty string

queue = deque([root])Queue to reconstruct tree level by level

node = queue.popleft()Process nodes level by level

if node:If node exists, record value and enqueue children

vals.append(str(node.val))Record node value as string

queue.append(node.left)Add left child to queue

queue.append(node.right)Add right child to queue

vals.append('X')Mark null children explicitly

while vals and vals[-1] == 'X':Trim trailing null markers to optimize string

vals = data.split(',')Split serialized string for deserialization

if vals[i] != 'X':Create right child if not null marker

import java.util.*;

public class Codec {
    private static final String NULL = "X";
    private static final String SEP = ",";

    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(node.val).append(SEP);
            queue.offer(node.left);
            queue.offer(node.right);
        }
        // Remove trailing nulls
        String res = sb.toString();
        while (res.endsWith(NULL + SEP)) {
            res = res.substring(0, res.length() - (NULL + SEP).length());
        }
        return res;
    }

    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] vals = data.split(SEP);
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (i < vals.length) {
                if (!vals[i].equals(NULL)) {
                    node.left = new TreeNode(Integer.parseInt(vals[i]));
                    queue.offer(node.left);
                }
                i++;
            }
            if (i < vals.length) {
                if (!vals[i].equals(NULL)) {
                    node.right = new TreeNode(Integer.parseInt(vals[i]));
                    queue.offer(node.right);
                }
                i++;
            }
        }
        return root;
    }

    // TreeNode class
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // Example usage:
    // Codec codec = new Codec();
    // String s = codec.serialize(root);
    // TreeNode root = codec.deserialize(s);
}

Line Notes

import java.util.*;Import utilities for queue and collections

if (root == null) return "";Handle empty tree by returning empty string

Queue<TreeNode> queue = new LinkedList<>();Queue for BFS traversal

TreeNode node = queue.poll();Process nodes level by level

if (node == null)If node is null, append null marker

sb.append(NULL).append(SEP);Append null marker for missing nodes

sb.append(node.val).append(SEP);Append node value to string builder

queue.offer(node.left);Add left child to queue

queue.offer(node.right);Add right child to queue

while (res.endsWith(NULL + SEP)) {Trim trailing null markers to optimize output

String[] vals = data.split(SEP);Split serialized string for deserialization

queue.offer(root);Initialize queue for reconstruction

if (!vals[i].equals(NULL)) {Create right child if not null marker

#include <iostream>
#include <string>
#include <sstream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "";
        queue<TreeNode*> q;
        q.push(root);
        string res;
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (node) {
                res += to_string(node->val) + ",";
                q.push(node->left);
                q.push(node->right);
            } else {
                res += "X,";
            }
        }
        // Trim trailing 'X,'
        while (res.size() >= 2 && res.substr(res.size() - 2) == "X,") {
            res.erase(res.size() - 2);
        }
        return res;
    }

    TreeNode* deserialize(const string& data) {
        if (data.empty()) return nullptr;
        istringstream in(data);
        string val;
        vector<string> vals;
        while (getline(in, val, ',')) {
            vals.push_back(val);
        }
        TreeNode* root = new TreeNode(stoi(vals[0]));
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (i < (int)vals.size()) {
                if (vals[i] != "X") {
                    node->left = new TreeNode(stoi(vals[i]));
                    q.push(node->left);
                }
                i++;
            }
            if (i < (int)vals.size()) {
                if (vals[i] != "X") {
                    node->right = new TreeNode(stoi(vals[i]));
                    q.push(node->right);
                }
                i++;
            }
        }
        return root;
    }
};

// Example usage:
// Codec codec;
// string s = codec.serialize(root);
// TreeNode* root = codec.deserialize(s);

Line Notes

#include <queue>Include queue for BFS traversal

if (!root) return "";Handle empty tree by returning empty string

queue<TreeNode*> q;Queue for reconstruction

TreeNode* node = q.front();Process nodes level by level

q.pop();Pop node from queue

if (node) {If node exists, append value and enqueue children

res += to_string(node->val) + ",";Append node value to result string

q.push(node->left);Add left child to queue

q.push(node->right);Add right child to queue

res += "X,";Append null marker for missing nodes

while (res.size() >= 2 && res.substr(res.size() - 2) == "X,") {Trim trailing null markers

vector<string> vals;Store split serialized values

if (vals[i] != "X") {Create right child if not null marker

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Codec {
    serialize(root) {
        if (!root) return '';
        const queue = [root];
        const vals = [];
        while (queue.length > 0) {
            const node = queue.shift();
            if (node === null) {
                vals.push('X');
                continue;
            }
            vals.push(node.val.toString());
            queue.push(node.left);
            queue.push(node.right);
        }
        while (vals.length > 0 && vals[vals.length - 1] === 'X') {
            vals.pop();
        }
        return vals.join(',');
    }

    deserialize(data) {
        if (!data) return null;
        const vals = data.split(',');
        const root = new TreeNode(parseInt(vals[0]));
        const queue = [root];
        let i = 1;
        while (queue.length > 0) {
            const node = queue.shift();
            if (i < vals.length) {
                if (vals[i] !== 'X') {
                    node.left = new TreeNode(parseInt(vals[i]));
                    queue.push(node.left);
                }
                i++;
            }
            if (i < vals.length) {
                if (vals[i] !== 'X') {
                    node.right = new TreeNode(parseInt(vals[i]));
                    queue.push(node.right);
                }
                i++;
            }
        }
        return root;
    }
}

// Example usage:
// const codec = new Codec();
// const s = codec.serialize(root);
// const root = codec.deserialize(s);

Line Notes

if (!root) return '';Handle empty tree by returning empty string

const queue = [root];Queue for reconstruction

const node = queue.shift();Process nodes level by level

if (node === null)If node is null, append null marker

vals.push('X');Mark null nodes explicitly

vals.push(node.val.toString());Append node value to output array

queue.push(node.left);Add left child to queue

queue.push(node.right);Add right child to queue

while (vals.length > 0 && vals[vals.length - 1] === 'X') {Trim trailing null markers

const vals = data.split(',');Split serialized string for deserialization

if (vals[i] !== 'X') {Create right child if not null marker

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once during BFS serialization and deserialization. The queue and output string scale linearly with the number of nodes.

💡 For 20 nodes, this means about 20 enqueue and dequeue operations per traversal, which is efficient and intuitive.

Interview Verdict: Accepted

This BFS approach is accepted and often preferred when the interviewer wants a level order representation or array-like serialization.

📊

All Approaches - One-Glance Tradeoffs

💡 The recursive preorder approach is simplest and most commonly coded in interviews. Iterative stack method is useful for deep trees. BFS approach matches array representation and is intuitive for some.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Recursive Preorder with Null Markers	O(n)	O(n)	Yes (deep recursion)	Yes	Code this approach in most interviews
2. Iterative Preorder with Stack	O(n)	O(n)	No	Yes	Mention or code if recursion depth is a concern
3. Level Order (BFS) with Null Markers	O(n)	O(n)	No	Yes	Mention if interviewer prefers array-like serialization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem and constraints, then explain the brute force approach clearly. Progress to iterative or BFS methods if asked. Practice coding and testing edge cases.

How to Present

Step 1: Clarify input/output format and ask about null node representation.Step 2: Describe the brute force recursive preorder traversal with null markers.Step 3: Write code for serialization and deserialization using recursion.Step 4: Discuss iterative stack-based approach if recursion depth is a concern.Step 5: Present BFS level order serialization if interviewer prefers array-like format.Step 6: Test your code with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, recursion, handling null nodes, and ability to reconstruct the exact tree. They also check if you can optimize or provide iterative solutions.

Common Follow-ups

• Can you serialize/deserialize a tree with random pointers? → Use additional data structures to store pointers.
• How to handle very large trees without stack overflow? → Use iterative methods.
• Can you compress the serialization string? → Use encoding or remove redundant nulls.
• How to serialize/deserialize N-ary trees? → Modify traversal and null markers accordingly.

💡 These follow-ups test your ability to adapt the solution to more complex scenarios or optimize for performance and memory.

🔍

Pattern Recognition

When to Use

1) You need to convert a tree to a string and back. 2) The problem mentions serialization or deserialization. 3) Null children must be handled explicitly. 4) The tree structure must be preserved exactly.

Signature Phrases

serialize a binary treedeserialize the string back to treenull markerspreorder traversal

NOT This Pattern When

Problems that only traverse trees without reconstructing or encoding, or that serialize graphs instead of trees.

Similar Problems

Binary Tree Inorder Traversal - related traversal techniqueConstruct Binary Tree from Preorder and Inorder Traversal - reconstruct tree from traversals

Practice

1. Consider the following iterative postorder traversal code to compute the diameter of a binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final value of the variable diameter after the function completes?

easy

A. 2

B. 4

C. 1

D. 3

Solution

1. Step 1: Trace heights and diameter updates for each node.

   Node 4: height=1, diameter=0; Node 2: left=1 (node4), right=0, diameter=max(0,1)=1; Node 3: height=1, diameter=1; Node 1: left=2 (node2), right=1 (node3), diameter=max(1,2+1=3)=3.

2. Step 2: Verify final diameter value returned.

   The diameter is the maximum sum of left and right heights at any node, which is 3 edges, so the longest path length is 3 edges.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest path is from node 4 to node 3 with length 3 edges [OK]

Hint: Diameter counts edges, not nodes [OK]

Common Mistakes:

• Confusing diameter as number of nodes
• Off-by-one in height calculation
• Missing right subtree height

2. You are given a binary tree and a target sum. The task is to find all root-to-leaf paths where the sum of the node values equals the target sum. Which algorithmic approach guarantees finding all such paths efficiently?

easy

A. Greedy traversal choosing the child with the closest value to the remaining sum

B. Depth-first search (DFS) with path tracking and backtracking to explore all root-to-leaf paths

C. Dynamic programming to store sums at each node and combine results bottom-up

D. Breadth-first search (BFS) with queue to find the shortest path matching the sum

Solution

1. Step 1: Understand problem requires all root-to-leaf paths

   Since we must find all paths, not just one, exhaustive exploration is needed.

2. Step 2: Identify DFS with path tracking and backtracking

   DFS explores each path fully, tracking the current path and sum, backtracking to explore alternatives.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS explores all paths, greedy or BFS do not guarantee all paths [OK]

Hint: All root-to-leaf paths require exhaustive DFS [OK]

Common Mistakes:

• Thinking greedy or BFS finds all paths
• Confusing DP for path enumeration

3. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

4. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?

medium

A. O(n) due to storing all nodes in a list during traversal

B. O(1) because the algorithm modifies the tree in-place without extra memory

C. O(log n) because the tree height is always balanced and recursion stack is limited

D. O(h) due to recursion stack depth in worst case of skewed tree

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.

2. Step 2: Clarify why O(h) not O(1) or O(n)

   It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack space equals tree height h [OK]

Hint: Recursion stack space equals tree height h [OK]

Common Mistakes:

• Assuming O(1) space because of in-place modification
• Confusing recursion stack with explicit data structures
• Assuming balanced tree always so O(log n) space

5. Suppose the problem is extended: the tree nodes can have duplicate values, and you want to check if the tree is symmetric ignoring node values, only structure matters. Which modification to the original DFS approach correctly solves this variant?

hard

A. Keep the value comparison but add a hash map to track visited nodes to avoid duplicates.

B. Use BFS level-order traversal and check if each level forms a palindrome of node values.

C. Modify the base case to return true if both nodes are null, and skip the value comparison step entirely.

D. Perform a preorder traversal and compare the traversal list with its reverse.

Solution

1. Step 1: Understand the variant ignores node values, only structure matters

   Therefore, the value comparison step must be removed to avoid false negatives due to duplicates.

2. Step 2: Modify the DFS to only check if both nodes exist or are null, recursively comparing mirrored subtrees

   Return true if both nodes are null; otherwise, recurse on mirrored children without comparing values.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Ignoring values means skipping value checks but preserving mirrored structure checks [OK]

Hint: Ignore values, check only mirrored structure recursively [OK]

Common Mistakes:

• Keeping value checks causing false negatives
• Using BFS palindrome checks which fail on structure
• Using preorder traversal which ignores mirrored structure