Bird
Raised Fist0
Interview Preptree-dfshardFacebookAmazonGoogleMicrosoft

Serialize and Deserialize Binary Tree

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Recursive Preorder with Null MarkersO(n)O(n)Yes (deep recursion)YesCode this approach in most interviews
2. Iterative Preorder with StackO(n)O(n)NoYesMention or code if recursion depth is a concern
3. Level Order (BFS) with Null MarkersO(n)O(n)NoYesMention 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/5)
1. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
easy
A. 2
B. 0
C. 3
D. 1

Solution

  1. Step 1: Trace dfs on leaf nodes 1 and 2

    Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.
  2. Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here

    Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    One camera at root covers all nodes [OK]
Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]
Common Mistakes:
  • Counting cameras on leaves instead of parent
  • Forgetting to add camera at root if uncovered
  • Misinterpreting coverage states
2. Consider the following iterative DFS code snippet for counting paths with sum equal to targetSum in a binary tree. Given the tree with root value 1, left child 2, right child 3, and targetSum = 3, what is the final value of result after the loop finishes?
class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                prefix_counts[current_sum] -= 1

        return result
easy
A. 1
B. 0
C. 3
D. 2

Solution

  1. Step 1: Trace initial stack and prefix_counts

    Start with stack=[(1,0,False)], prefix_counts={0:1}, result=0.
  2. Step 2: Process nodes and update result

    Paths summing to 3 are: (1->2) and (3) alone, total 2 paths counted.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Two valid paths found matching target sum [OK]
Hint: Count paths by prefix sums during DFS traversal [OK]
Common Mistakes:
  • Missing the single node path (3)
  • Double counting paths due to prefix_counts not decremented
  • Off-by-one in updating result
3. What is the time complexity of the iterative postorder traversal using one stack and a pointer on a binary tree with n nodes?
medium
A. O(n log n) due to repeated stack operations
B. O(n) but with O(h) auxiliary space where h is tree height
C. O(n^2) because of nested while loops
D. O(n) because each node is visited and processed once

Solution

  1. Step 1: Analyze node visits

    Each node is pushed and popped exactly once, so operations proportional to n.
  2. Step 2: Confirm no nested repeated work

    Inner loops traverse down left children, but total iterations over all nodes sum to n.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Linear time complexity matches traversal of all nodes once [OK]
Hint: Each node processed once -> O(n) time [OK]
Common Mistakes:
  • Assuming nested loops multiply to n^2
  • Confusing auxiliary space with time
4. Suppose the problem is modified so that you can rob the same node multiple times (i.e., nodes can be reused any number of times), but still cannot rob directly connected nodes simultaneously. Which modification to the algorithm is necessary to correctly solve this variant?
hard
A. Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse.
B. Use the same DFS with two-value return; no changes needed since adjacency constraints remain.
C. Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection.
D. Modify the DFS to allow revisiting nodes multiple times and use memoization keyed by node and robbing state.

Solution

  1. Step 1: Understand the reuse constraint

    Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.
  2. Step 2: Identify necessary algorithmic change

    We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.
  3. Step 3: Why other options fail

    Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Memoization with extended state handles reuse and adjacency constraints [OK]
Hint: Reuse requires stateful memoization, not simple DFS [OK]
Common Mistakes:
  • Assuming original DFS suffices for reuse
  • Ignoring adjacency constraints when reusing nodes
5. Suppose the problem is modified so that node values can be negative integers, and the goal remains to sum all root-to-leaf numbers formed by concatenation (including negative signs). Which of the following changes to the algorithm is necessary to handle this correctly?
hard
A. Skip negative nodes since they break number formation
B. Continue using integer arithmetic with multiplication by 10, ignoring signs
C. Add absolute values of node.val to current_number to avoid sign issues
D. Use string concatenation of node values along the path and convert to integer at leaf nodes

Solution

  1. Step 1: Understand impact of negative values

    Integer arithmetic with multiplication by 10 assumes digits 0-9; negative signs break this assumption.
  2. Step 2: Identify correct approach

    Concatenating node values as strings preserves negative signs and digit order; convert to integer only at leaf nodes.
  3. Step 3: Confirm other options fail

    Ignoring signs or skipping negatives leads to incorrect sums or incomplete paths.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    String concatenation handles negative digits correctly [OK]
Hint: Use string concatenation for negative digits [OK]
Common Mistakes:
  • Assuming all digits are positive
  • Using arithmetic without sign handling
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard