161. Build and Serialize a Binary Tree

Why this mechanism works

The representation describes pending child slots of real parents, not array indices in a complete tree. A queue holds those parents in level order. Serialization reverses this process: emit a missing marker for a missing child, but never expand that marker into further slots. Trimming only trailing markers produces a canonical representation.

State and boundaries

The build queue contains real nodes whose child slots are unfilled. The serialization queue contains the next real or missing slots to emit.

Protocol

1. Create the root unless input is empty or begins with None.
2. For each queued parent consume its next two child entries.
3. Create and enqueue nonmissing children.
4. Serialize by FIFO slot traversal.
5. Trim trailing missing markers.

Visualization

values [1,None,2,3]
    1
     \
      2
     /
    3
3 fills node 2's left slot, not an absent parent's slot

Python implementation

from collections import deque
from structures import TreeNode

def build_binary_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        parent = queue.popleft()
        for side in ('left', 'right'):
            if i == len(values):
                break
            value = values[i]
            i += 1
            if value is not None:
                child = TreeNode(value)
                setattr(parent, side, child)
                queue.append(child)
    return root

def serialize_binary_tree(root):
    output, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        output.append(None if node is None else node.val)
        if node is not None:
            queue.extend((node.left, node.right))
    while output and output[-1] is None:
        output.pop()
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 build_binary_tree: if not values or values[0] is None:
values=[1, None, 2, 3]

L7 build_binary_tree: root = TreeNode(values[0])
values=[1, None, 2, 3]; root=N1(val=1,left=None,right=None)

L8 build_binary_tree: queue = deque([root])
values=[1, None, 2, 3]; root=N1(val=1,left=None,right=None); queue=deque([N1(val=1,left=None,right=None)])

L9 build_binary_tree: i = 1
values=[1, None, 2, 3]; root=N1(val=1,left=None,right=None); queue=deque([N1(val=1,left=None,right=None)]); i=1

L11 build_binary_tree: parent = queue.popleft()
values=[1, None, 2, 3]; root=N1(val=1,left=None,right=None); queue=deque([]); i=1; parent=N1(val=1,left=None,right=None)

L12 build_binary_tree: for side in ('left', 'right'):
values=[1, None, 2, 3]; root=N1(val=1,left=None,right=None); queue=deque([]); i=1; parent=N1(val=1,left=None,right=None); side='left'

L15 build_binary_tree: value = values[i]
values=[1, None, 2, 3]; root=N1(val=1,left=None,right=None); queue=deque([]); i=1; parent=N1(val=1,left=None,right=None); side='left'; value=None

L16 build_binary_tree: i += 1
values=[1, None, 2, 3]; root=N1(val=1,left=None,right=None); queue=deque([]); i=2; parent=N1(val=1,left=None,right=None); side='left'; value=None

... 31 intermediate state changes omitted ...

L27 serialize_binary_tree: output.append(None if node is None else node.val)
root=N1(val=1,left=None,right=N2); output=[1, None, 2, 3, None, None, None]; queue=deque([]); node=None

L31 serialize_binary_tree: output.pop()
root=N1(val=1,left=None,right=N2); output=[1, None, 2, 3, None, None]; queue=deque([]); node=None

L31 serialize_binary_tree: output.pop()
root=N1(val=1,left=None,right=N2); output=[1, None, 2, 3, None]; queue=deque([]); node=None

L31 serialize_binary_tree: output.pop()
root=N1(val=1,left=None,right=N2); output=[1, None, 2, 3]; queue=deque([]); node=None

L5 build_binary_tree: if not values or values[0] is None:
values=[]

L24 serialize_binary_tree: output, queue = [], deque([root])
root=None; output=[]; queue=deque([None])

L26 serialize_binary_tree: node = queue.popleft()
root=None; output=[]; queue=deque([]); node=None

L27 serialize_binary_tree: output.append(None if node is None else node.val)
root=None; output=[None]; queue=deque([]); node=None

L31 serialize_binary_tree: output.pop()
root=None; output=[]; queue=deque([]); node=None

Why the solution is correct

Each consumed entry is attached to the next slot in the specified level order, so construction preserves every supplied relationship. Serialization visits those same slots in the same order. Removing trailing missing slots cannot change any real node's position or relationships. Both queues process finitely many nodes and slots.

Time and space

O(n) time and O(n) output/queue space for n real nodes, with at most 2n+1 serialized slots before trimming.

Common mistakes

Using children at 2*i+1 and 2*i+2 interprets a different representation when missing parents occur. Expanding None nodes during serialization creates endless empty descendants.

Reasoning card

Transfer exercise

Design a preorder format with explicit missing markers. Explain why omitting those interior markers would lose tree shape.