Serialize and Deserialize Binary Tree

▶

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.

fill_cells

Dequeue node 1, append its value, enqueue children

Node 1 is dequeued, its value '1' is appended to the serialized list, and its children nodes 2 and 3 are enqueued.

💡 Processing the current node and adding its children to the queue ensures all nodes are visited in level order.

Line:

node = queue.popleft()
vals.append(str(node.val))
queue.append(node.left)
queue.append(node.right)

💡 Appending node values and enqueuing children maintains BFS order and records tree structure.

fill_cells

Dequeue node 2, append its value, enqueue null children

Node 2 is dequeued, its value '2' is appended, and its null children are enqueued as None placeholders.

💡 Null children are enqueued as None to mark missing nodes explicitly in serialization.

Line:

node = queue.popleft()
vals.append(str(node.val))
queue.append(node.left)
queue.append(node.right)

💡 Including null children as placeholders preserves tree shape in the serialized string.

fill_cells

Dequeue node 3, append its value, enqueue children 4 and 5

Node 3 is dequeued, its value '3' is appended, and its children nodes 4 and 5 are enqueued.

💡 Adding children of node 3 continues BFS traversal and records deeper tree levels.

Line:

node = queue.popleft()
vals.append(str(node.val))
queue.append(node.left)
queue.append(node.right)

💡 Queue now contains nodes representing the next level of the tree.

fill_cells

Dequeue null, append 'X' for missing child

A null node is dequeued, so 'X' is appended to the serialized list to mark a missing child.

💡 Null markers are crucial to preserve the exact tree shape during serialization.

Line:

if node:
  ...
else:
  vals.append('X')

💡 Null children are explicitly recorded to differentiate missing nodes from existing ones.

fill_cells

Dequeue null, append 'X' for missing child

Another null node is dequeued, appending another 'X' to represent the second missing child of node 2.

💡 Each null child must be recorded to maintain the correct tree structure in serialization.

Line:

if node:
  ...
else:
  vals.append('X')

💡 Two consecutive 'X's indicate both children of node 2 are missing.

fill_cells

Dequeue node 4, append its value, enqueue null children

Node 4 is dequeued, its value '4' is appended, and its null children are enqueued.

💡 Leaves are processed similarly, with null children marked explicitly.

Line:

node = queue.popleft()
vals.append(str(node.val))
queue.append(node.left)
queue.append(node.right)

💡 Leaves are handled the same way, ensuring full tree representation.

fill_cells

Dequeue node 5, append its value, enqueue null children

Node 5 is dequeued, its value '5' is appended, and its null children are enqueued.

💡 Processing the last non-null node before trailing nulls.

Line:

node = queue.popleft()
vals.append(str(node.val))
queue.append(node.left)
queue.append(node.right)

💡 Leaves at the last level are handled the same way, ensuring full tree representation.

prune

Trim trailing 'X's from serialized list

Trailing 'X' markers are removed from the serialized list to produce a compact string representation.

💡 Removing unnecessary null markers reduces the serialized string size without losing tree structure information.

Line:

while vals and vals[-1] == 'X':
  vals.pop()

💡 Trailing nulls beyond the last non-null node do not affect deserialization and can be safely removed.

setup

Initialize deserialization: create root node

Deserialization starts by splitting the serialized string and creating the root node with value 1.

💡 The first value always represents the root node in level order deserialization.

Line:

vals = data.split(',')
root = TreeNode(int(vals[0]))
queue = deque([root])
i = 1

💡 Root node is the starting point for reconstructing the tree.

insert

Assign left child of node 1

Node 1 is dequeued; next value '2' creates left child node 2, which is enqueued.

💡 Assigning children level by level reconstructs the original tree structure.

Line:

node = queue.popleft()
if vals[i] != 'X':
  node.left = TreeNode(int(vals[i]))
  queue.append(node.left)
i += 1

💡 Non-null values create new nodes and extend the queue for further child assignments.

insert

Assign right child of node 1

Next value '3' creates right child node 3 of node 1, which is enqueued.

💡 Assigning right child completes node 1's children before moving on.

Line:

if vals[i] != 'X':
  node.right = TreeNode(int(vals[i]))
  queue.append(node.right)
i += 1

💡 Both children of a node are assigned before dequeuing the next node.

insert

Assign children of node 2 (both null)

Node 2 is dequeued; next two values are 'X' and 'X', so no children are created.

💡 Null markers indicate missing children, so no nodes are enqueued.

Line:

node = queue.popleft()
if vals[i] != 'X': ... else skip
if vals[i] != 'X': ... else skip

💡 Null children are correctly interpreted to avoid creating nodes.

insert

Assign left child of node 3

Node 3 is dequeued; next value '4' creates left child node 4, which is enqueued.

💡 Non-null value creates a new node and extends the queue for further child assignments.

Line:

if vals[i] != 'X':
  node.left = TreeNode(int(vals[i]))
  queue.append(node.left)
i += 1

💡 Children are assigned in order, preserving tree structure.

insert

Assign right child of node 3

Next value '5' creates right child node 5 of node 3, which is enqueued.

💡 Assigning right child completes node 3's children before moving on.

Line:

if vals[i] != 'X':
  node.right = TreeNode(int(vals[i]))
  queue.append(node.right)
i += 1

💡 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.

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. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

easy

A. True

B. False

C. Raises an exception due to null pointer

D. Returns True only if the root value equals targetSum

Solution

1. Step 1: Trace the path sums

   Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.

2. Step 2: Confirm code logic

   The DFS returns True as soon as it finds the matching path sum at a leaf node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Path 5↔4↔11↔2 sums to 22, so return True [OK]

Hint: Check all root-to-leaf paths, not just partial sums [OK]

Common Mistakes:

• Stopping at non-leaf nodes
• Ignoring leaf node condition

2. 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

3. 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

4. Consider the following buggy code for inverting a binary tree. Which line contains the subtle bug that causes incorrect inversion?

medium

A. Line 3: Swapping children before recursive calls

B. Line 5: Recursive call on right child

C. Line 4: Recursive call on left child

D. Line 2: Missing check for empty tree

Solution

1. Step 1: Analyze order of operations

   The code swaps children before recursively inverting subtrees, which means subtrees are swapped but not inverted themselves.

2. Step 2: Identify why swapping before recursion is incorrect

   Swapping first causes recursion to invert the wrong subtrees, leading to partial or incorrect inversion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping must happen after recursive calls to invert subtrees correctly [OK]

Hint: Swap after recursion, not before, to invert subtrees properly [OK]

Common Mistakes:

• Swapping children before recursion
• Ignoring null root checks
• Confusing left and right subtree recursion order

5. Consider the following buggy code for checking if a binary tree is symmetric. Which line contains the subtle bug that causes incorrect results for asymmetric trees?

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return True
        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

medium

A. Line 5: if t1.val != t2.val: return False

B. Line 3: if not t1 or not t2: return True

C. Line 6: return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

D. Line 8: return isMirror(root.left, root.right) if root else True

Solution

1. Step 1: Analyze base case for null nodes

   The line returns true if either t1 or t2 is null, but it should only return true if both are null.

2. Step 2: Identify that returning true when only one node is null causes false positives

   This causes asymmetric trees with missing nodes on one side to be incorrectly considered symmetric.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Base case must check both nodes null equality, not just one [OK]

Hint: Base case must return true only if both nodes are null [OK]

Common Mistakes:

• Returning true if only one node is null
• Forgetting to check node values before recursion
• Mixing left and right subtree comparisons