💡 Both children of node 3 are assigned, preserving the original tree shape.
insert
Assign children of node 4 and node 5 (all null), finish deserialization
Nodes 4 and 5 are dequeued; no more values remain, so no children are assigned, completing reconstruction.
💡 No more values means leaves have no children, finalizing the tree.
Line:while queue:
node = queue.popleft()
if i < len(vals): ...
💡 Deserialization completes when all nodes have been assigned children or no more values remain.
from collections import deque
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):
if not root:
return '' # STEP 1
queue = deque([root]) # STEP 1
vals = []
while queue: # STEP 2-12
node = queue.popleft() # STEP 2-12
if node: # STEP 2-12
vals.append(str(node.val)) # STEP 2-12
queue.append(node.left) # STEP 2-12
queue.append(node.right) # STEP 2-12
else:
vals.append('X') # STEP 5,6,9-12
while vals and vals[-1] == 'X': # STEP 13
vals.pop() # STEP 13
return ','.join(vals) # STEP 13
def deserialize(self, data):
if not data:
return None # STEP 10
vals = data.split(',') # STEP 10
root = TreeNode(int(vals[0])) # STEP 10
queue = deque([root]) # STEP 10
i = 1
while queue: # STEP 11-16
node = queue.popleft() # STEP 11-16
if i < len(vals):
if vals[i] != 'X': # STEP 11-16
node.left = TreeNode(int(vals[i])) # STEP 11-16
queue.append(node.left) # STEP 11-16
i += 1
if i < len(vals):
if vals[i] != 'X': # STEP 11-16
node.right = TreeNode(int(vals[i])) # STEP 11-16
queue.append(node.right) # STEP 11-16
i += 1
return root # STEP 16
📊
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
Step 1: Understand traversal order requirement
The problem requires visiting root before left and right subtrees, which is preorder traversal.
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.
Final Answer:
Option C -> Option C
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
Step 1: Calculate tree height
Height h = 3 (nodes 1 -> 2 -> 4).
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.
Final Answer:
Option A -> Option A
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
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.
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.
Final Answer:
Option A -> Option A
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
Step 1: Trace isMirror on root.left and root.right nodes with value 2
Both nodes exist and have equal values, so recursion continues.
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.
Final Answer:
Option D -> Option D
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
Step 1: Identify auxiliary space usage
The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.
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.
Final Answer:
Option D -> Option D
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 unknownstrongwhile earning +1 Grip toward your certificate.