Bird
Raised Fist0
Interview Preptree-dfshardFacebookAmazonGoogleMicrosoft

Serialize and Deserialize Binary Tree

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize serialization queue with root node

Start serialization by placing the root node (value 1) into the queue to begin level order traversal.

💡 Initializing the queue with the root node is essential to start the BFS traversal.
Line:queue = deque([root])
💡 The queue controls the order nodes are processed, ensuring level order traversal.
📊
Serialize and Deserialize Binary Tree - Watch the Algorithm Execute, Step by Step
Watching each enqueue, dequeue, and node processing operation reveals how the algorithm preserves tree structure and handles nulls, making the process intuitive.
Step 1/16
·Active fill★Answer cell
Current node: 1
12345
BFS Queue
N1
Current node: 1
12345
BFS Queue
N2N3
Result: [1]
Current node: 2
12345
BFS Queue
N3NN
Result: [1, 2]
Current node: 3
12345
BFS Queue
NNN4N5
Result: [1, 2, 3]
12345
BFS Queue
NN4N5
Result: [1, 2, 3, X]
12345
BFS Queue
N4N5
Result: [1, 2, 3, X, X]
Current node: 4
12345
BFS Queue
N5NN
Result: [1, 2, 3, X, X, 4]
Current node: 5
12345
BFS Queue
NNNN
Result: [1, 2, 3, X, X, 4, 5]
12345
Result: [1, 2, 3, X, X, 4, 5]
Return: "1,2,3,X,X,4,5"
Current node: 1
1
BFS Queue
N1
Result: [1, 2, 3, X, X, 4, 5]
Current node: 1
12
BFS Queue
N2
Result: [1, 2, 3, X, X, 4, 5]
Current node: 1
123
BFS Queue
N2N3
Result: [1, 2, 3, X, X, 4, 5]
Current node: 2
123
BFS Queue
N3
Result: [1, 2, 3, X, X, 4, 5]
Current node: 3
1234
BFS Queue
N4
Result: [1, 2, 3, X, X, 4, 5]
Current node: 3
12345
BFS Queue
N4N5
Result: [1, 2, 3, X, X, 4, 5]
12345
Result: [1, 2, 3, X, X, 4, 5]
Return: {"root":1}

Key Takeaways

✓ Level order traversal with explicit null markers preserves the exact tree structure during serialization.

Seeing nulls enqueued and appended as 'X' clarifies how missing children are represented, which is hard to grasp from code alone.

✓ Trimming trailing null markers optimizes the serialized string without losing information.

Visualizing the removal of trailing 'X's shows how the algorithm balances completeness and compactness.

✓ Deserialization uses the queue to assign children level by level, reconstructing the tree exactly as it was.

Watching nodes dequeued and children assigned stepwise reveals how the serialized string maps back to the tree.

Practice

(1/5)
1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?
easy
A. Postorder traversal using two stacks
B. Level-order traversal using a queue
C. Morris preorder traversal using threaded binary tree
D. Inorder traversal using recursion

Solution

  1. Step 1: Understand traversal order requirement

    The problem requires visiting root before left and right subtrees, which is preorder traversal.
  2. Step 2: Identify approach with no extra space

    Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Preorder visits root first; Morris traversal achieves this with O(1) space [OK]
Hint: Preorder visits root before children [OK]
Common Mistakes:
  • Confusing inorder or postorder with preorder traversal
  • Assuming recursion is always needed
  • Using level-order which visits nodes by depth
2. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?
easy
A. 4
B. 3
C. 5
D. 6

Solution

  1. Step 1: Calculate tree height

    Height h = 3 (nodes 1 -> 2 -> 4).
  2. Step 2: Binary search on last level nodes

    Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]
Hint: Count = perfect nodes + last level nodes found [OK]
Common Mistakes:
  • Off-by-one in binary search bounds
  • Miscounting last level nodes
3. Given the following code for inverting a binary tree, what is the value of the left child of the root node after calling invertTree(root) on the tree below? Tree structure before inversion:

    2
   / \
  1   3
easy
A. 3
B. 1
C. 2
D. null

Solution

  1. Step 1: Trace recursive calls on root=2

    invertTree called on left child (1) and right child (3), both leaves, so their children are null and return immediately.
  2. Step 2: Swap left and right children of root=2

    After recursion, root.left and root.right are swapped: left becomes 3, right becomes 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Root's left child after inversion is original right child 3 [OK]
Hint: Swapping children after recursion flips subtree positions [OK]
Common Mistakes:
  • Confusing left and right child values after inversion
  • Forgetting to swap after recursive calls
  • Assuming root value changes
4. Given the following code snippet for checking if a binary tree is symmetric, what is the final return value when called with the tree root = TreeNode(1, TreeNode(2), TreeNode(2))?
from typing import Optional

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

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return t1 == t2
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

root = TreeNode(1, TreeNode(2), TreeNode(2))
print(isSymmetric(root))  # What is the output?
easy
A. false
B. Raises an exception
C. null
D. true

Solution

  1. Step 1: Trace isMirror on root.left and root.right nodes with value 2

    Both nodes exist and have equal values, so recursion continues.
  2. Step 2: Recursively check left.left vs right.right and left.right vs right.left (both null)

    Since both pairs are null, isMirror returns true for these calls, so overall returns true.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Symmetric tree with equal child nodes returns true [OK]
Hint: Symmetric tree with equal children returns true [OK]
Common Mistakes:
  • Confusing null checks causing exceptions
  • Returning false prematurely on equal nodes
  • Misreading recursion base cases
5. 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
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