Bird
Raised Fist0
Interview Preptree-dfshardFacebookAmazonGoogleMicrosoft

Serialize and Deserialize Binary Tree

Choose your preparation mode4 modes available
📋
Problem

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?

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.
Edge cases: Empty tree → should serialize to an empty string or a special marker and deserialize to nullTree with only left children → serialization must correctly represent null right childrenTree with only right children → serialization must correctly represent null left children
</>
IDE
def serialize(root: Optional[TreeNode]) -> str: pass def deserialize(data: str) -> Optional[TreeNode]: passpublic String serialize(TreeNode root) { // ... } public TreeNode deserialize(String data) { // ... }string serialize(TreeNode* root) { // ... } TreeNode* deserialize(const string& data) { // ... }function serialize(root) { // ... } function deserialize(data) { // ... }
def serialize(root):
    # Write your solution here
    pass

def deserialize(data):
    # Write your solution here
    pass
class Codec {
    public String serialize(TreeNode root) {
        // Write your solution here
        return "";
    }
    public TreeNode deserialize(String data) {
        // Write your solution here
        return null;
    }
}
#include <string>
using namespace std;

string serialize(TreeNode* root) {
    // Write your solution here
    return "";
}

TreeNode* deserialize(const string& data) {
    // Write your solution here
    return nullptr;
}
function serialize(root) {
    // Write your solution here
}

function deserialize(data) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: Missing 'X' markers for null childrenNot adding null markers during serialization, causing deserialization to fail or produce incorrect trees.✅ Add 'X' for every null child node during preorder traversal serialization.
Wrong: Incorrect traversal order in serializationUsing inorder or postorder traversal instead of preorder, breaking deserialization assumptions.✅ Use preorder traversal: node, left subtree, right subtree.
Wrong: Negative or zero values serialized incorrectlyConverting integers to strings improperly or ignoring sign, causing wrong deserialization.✅ Convert node values to strings with str() and parse with int() preserving sign.
Wrong: Empty tree serialized as empty string instead of 'X'Not handling null root case explicitly in serialization.✅ Return 'X' when root is null to represent empty tree.
Wrong: TLE on large inputsUsing exponential or quadratic time algorithms instead of linear traversal.✅ Implement O(n) preorder traversal with null markers for serialization and deserialization.
✓
Test Cases
t1_01basic
Input{"root":[1,2,3,null,null,4,5]}
Expected"1,2,X,X,3,4,X,X,5,X,X"

Preorder serialization with 'X' as null marker for the tree [1,2,3,null,null,4,5]. Deserializing reconstructs the exact same tree.

t1_02basic
Input{"root":[10,5,15,null,7,null,20]}
Expected"10,5,X,7,X,X,15,X,20,X,X"

Preorder serialization of tree with mixed null children: root=10, left=5 with right child 7, right=15 with right child 20.

t2_01edge
Input{"root":null}
Expected"X"

Empty tree serializes to 'X' and deserializes back to null.

t2_02edge
Input{"root":[42]}
Expected"42,X,X"

Single node tree serializes to value plus two null markers for children.

t2_03edge
Input{"root":[1,2,null,3]}
Expected"1,2,3,X,X,X,X"

Tree with only left children: 1->2->3, right children are null and must be marked.

t3_01corner
Input{"root":[1,null,2,null,3]}
Expected"1,X,2,X,3,X,X"

Right skewed tree: 1->2->3 with null left children must be serialized correctly.

t3_02corner
Input{"root":[0,-1,1]}
Expected"0,-1,X,X,1,X,X"

Tree with zero and negative values must serialize and deserialize preserving sign and value.

t3_03corner
Input{"root":[1,2,3,4,5,6,7]}
Expected"1,2,4,X,X,5,X,X,3,6,X,X,7,X,X"

Full binary tree to test correct preorder traversal and null markers for leaves.

t4_01performance
Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}
⏱ Performance - must finish in 2000ms

Performance test with n=100 nodes in a balanced tree structure. Serialization and deserialization must run in O(n) time within 2 seconds.

Practice

(1/5)
1. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?
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
easy
A. [2, 3, 1]
B. [1, 3, 2]
C. [3, 2, 1]
D. [3, 1, 2]

Solution

  1. Step 1: Trace traversal on given tree

    Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.
  2. Step 2: Process nodes in postorder

    3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Output matches postorder [3, 2, 1] [OK]
Hint: Postorder output for this tree is [3,2,1] [OK]
Common Mistakes:
  • Confusing order of appending nodes
  • Off-by-one in stack popping
2. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?
easy
A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.
B. Use dynamic programming to store sums of subtrees and combine results bottom-up.
C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.
D. Use a greedy approach to prune paths that exceed the target sum early.

Solution

  1. Step 1: Understand problem constraints and path definition

    The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.
  2. Step 2: Recognize prefix sum with DFS pattern

    Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Prefix sum + DFS solves in linear time [OK]
Hint: Prefix sums track cumulative sums efficiently [OK]
Common Mistakes:
  • Assuming paths must start at root or leaf
  • Using brute force DFS from every node without pruning
  • Trying greedy pruning which fails on negative values
3. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Depth-first search (DFS) with early stopping upon finding a valid path
B. Greedy traversal choosing the child with the closest value to the target sum
C. Dynamic programming with memoization of partial sums at each node
D. Breadth-first search (BFS) exploring all paths level by level

Solution

  1. Step 1: Understand the problem constraints

    The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.
  2. Step 2: Identify the best approach

    DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS explores paths fully and stops early when possible [OK]
Hint: Early stopping DFS avoids unnecessary traversal [OK]
Common Mistakes:
  • Believing greedy approach works for sums
  • Confusing BFS with DFS for path sums
4. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and node values can be negative. Which of the following approaches correctly adapts the maximum path sum algorithm to handle this variant?
hard
A. Use the same postorder traversal with global max tracking, ignoring negative gains as before.
B. Detect cycles and use dynamic programming with memoization to avoid infinite loops, allowing repeated nodes in paths.
C. Convert the tree to a graph and run Bellman-Ford algorithm to find the maximum sum path allowing cycles.
D. Use depth-first search with pruning to explore all paths, but limit path length to avoid infinite loops.

Solution

  1. Step 1: Understand the impact of allowing node reuse

    Allowing cycles means paths can revisit nodes infinitely, so naive DFS or postorder traversal fails due to infinite loops.
  2. Step 2: Identify correct approach

    Dynamic programming with cycle detection and memoization prevents infinite recursion and correctly computes max sums with repeated nodes.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Memoization with cycle detection handles repeated nodes safely [OK]
Hint: Cycle detection and memoization needed for repeated nodes [OK]
Common Mistakes:
  • Using same postorder traversal causes infinite loops
  • Bellman-Ford is for shortest paths, not max sums with negative cycles
  • DFS without cycle checks leads to infinite recursion
5. Suppose the Path Sum problem is modified so that node values can be negative, and you want to find if any root-to-leaf path sums exactly to targetSum. Which of the following changes to the DFS approach is necessary to handle this correctly?
hard
A. Precompute all path sums and store them in a hash set for O(1) lookup
B. Add memoization to avoid revisiting nodes with the same current sum
C. Use BFS instead of DFS to guarantee shortest path sum
D. Remove early stopping because negative values can invalidate pruning assumptions

Solution

  1. Step 1: Understand impact of negative values

    Negative values mean partial sums can decrease later, so pruning based on current sum is unsafe.
  2. Step 2: Adjust algorithm accordingly

    Early stopping based on partial sums must be removed to avoid missing valid paths.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Negative values break pruning assumptions, so early stopping must be disabled [OK]
Hint: Negative values invalidate pruning, so no early stopping [OK]
Common Mistakes:
  • Assuming early stopping always works
  • Switching to BFS unnecessarily
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