Building and serializing trees

Problem

You are handed the output of a traversal and asked for the tree, or asked to write a tree to a string and read it back. Three ideas cover the whole family. Reconstruct from two orders: preorder tells you the root first, inorder tells you how many nodes sit on its left. Serialize with markers: write a placeholder for each missing child so that one preorder or level-order list is unambiguous. Build a balanced tree from sorted input: choose the middle as the root so the two halves have nearly equal size. The maximum-path-sum question that is sometimes grouped here is solved on the tree depth-first search page, because it computes values on an existing tree rather than building one.

Intuition

Preorder is "root, then the entire left subtree, then the entire right subtree". So the first value is always the root, and after it come all the left-subtree values as one contiguous block, followed by the right-subtree block. What preorder does not say is where the left block ends. Inorder is "left subtree, root, right subtree", so once you find the root inside the inorder list, everything to its left is the left subtree and everything to its right is the right subtree. The inorder list supplies the size of the left block; preorder supplies the identity of each root. Together they determine the tree when the values are distinct.

Why one traversal is not enough: the preorder list 1, 2 is produced by both "1 with left child 2" and "1 with right child 2". The shape information is missing. Serialization fixes this differently: it records the missing children explicitly, so the list itself says exactly where each subtree stops. With markers, the list has a self-delimiting structure: after reading a node you recursively read its left subtree (which ends with its own markers) and then its right subtree, and you always know when you are done.

Amber is the root. Green is the left subtree's inorder block and blue is the right subtree's. The left block has 1 value, so the next 1 value after the root in preorder are the left subtree's own preorder.

Mechanics

Preorder plus inorder

Keep a cursor into the preorder list. The function build(lo, hi) builds the subtree whose inorder values occupy inorder[lo..hi]. If the range is empty, return None. Otherwise take preorder[cursor] as the root, advance the cursor, look up the root's index mid in inorder, build the left subtree from (lo, mid-1) and then the right from (mid+1, hi). The order matters: the cursor must finish consuming the left block before the right subtree reads its root, which is exactly the order preorder lists them. With a dictionary from value to inorder index, each call is O(1) plus recursion, so construction is O(n).

Correctness is induction on the range size. For an empty range the answer is empty. For a non-empty range, the next preorder value is the root of this subtree (preorder starts with the root), the inorder range splits at the root's index into the left and right value sets, and the recursive calls consume exactly those many preorder values, so the cursor lands on the right block for each. With inorder and postorder instead, the root is the last unread postorder value, so you read from the back and build the right subtree first.

Serialization with markers

Write a preorder walk that emits the value for a node and a marker (say #) for each missing child. A tree with n nodes has n+1 missing children, so the output has 2n+1 tokens. To read it back, consume tokens recursively: a marker returns None; a value creates a node whose left and right come from the next two recursive reads. Because the walk is deterministic, reading mirrors writing exactly, and the round trip returns the original tree. A level-order variant works the same way with a queue and is how many systems print trees; it is easier to read by eye and no harder to implement.

Balanced trees from sorted input

Given sorted values, any choice of root splits the array into a left part and a right part, and the inorder property of a search tree already holds. The only question is height. Choosing the middle makes the two parts differ in size by at most one, so the height is the ceiling of log₂(n+1). Choosing the first element would give a chain of height n. For a sorted linked list the same idea applies; find the middle with fast and slow pointers, or build bottom-up while consuming the list in order.

The tree above and its serialization below: green boxes are values, blue boxes are markers for missing children. The strip scrolls sideways on a narrow screen.

Worked example

Rebuilding. Preorder 3, 9, 20, 15, 7, inorder 9, 3, 15, 20, 7. Each row is one call, in the order the calls happen:

The first root is 3; it sits at inorder index 1, so 9 goes left and 15, 20, 7 goes right. The left block has one value, so the very next preorder value (9) is the entire left subtree. The right block then starts with the next preorder value, 20. The tree has root 3, left child 9 and right child 20, which has children 15 and 7.

Serializing. The preorder walk with markers produces 3 9 # # 20 15 # # 7 # #. The serialized string has 11 tokens for 5 nodes: 2n + 1, because every node contributes itself and each of the n + 1 empty child slots contributes a marker. Reading it back gives the same tree.

Balanced from sorted. For the sorted array -10, -3, 0, 5, 9: the middle element 0 becomes the root, so -10, -3 goes left and 5, 9 goes right. In the left half the middle (index 1 of two) is -3 with -10 to its left; in the right half it is 9 with 5 to its left. The height is 3, the minimum possible for 5 nodes.

Implementation

from collections import deque


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


def build_tree(preorder, inorder):
    index = {val: i for i, val in enumerate(inorder)}   # O(1) root lookup
    cursor = 0

    def build(lo, hi):
        nonlocal cursor
        if lo > hi:
            return None
        root = TreeNode(preorder[cursor])
        cursor += 1
        mid = index[root.val]
        root.left = build(lo, mid - 1)                   # must run before the right side
        root.right = build(mid + 1, hi)
        return root

    return build(0, len(inorder) - 1)


def build_tree_post(inorder, postorder):
    index = {val: i for i, val in enumerate(inorder)}
    cursor = len(postorder) - 1

    def build(lo, hi):
        nonlocal cursor
        if lo > hi:
            return None
        root = TreeNode(postorder[cursor])
        cursor -= 1
        mid = index[root.val]
        root.right = build(mid + 1, hi)                  # right first when reading from the back
        root.left = build(lo, mid - 1)
        return root

    return build(0, len(inorder) - 1)


def serialize(root):
    out = []

    def walk(node):
        if not node:
            out.append("#")
            return
        out.append(str(node.val))
        walk(node.left)
        walk(node.right)

    walk(root)
    return ",".join(out)


def deserialize(data):
    tokens = iter(data.split(","))

    def build():
        token = next(tokens)
        if token == "#":
            return None
        node = TreeNode(int(token))
        node.left = build()
        node.right = build()
        return node

    return build()


def serialize_levels(root):
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node:
            out.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            out.append("#")
    return ",".join(out)


def deserialize_levels(data):
    tokens = data.split(",")
    if tokens[0] == "#":
        return None
    root = TreeNode(int(tokens[0]))
    queue, i = deque([root]), 1
    while queue:
        node = queue.popleft()
        if tokens[i] != "#":
            node.left = TreeNode(int(tokens[i]))
            queue.append(node.left)
        i += 1
        if tokens[i] != "#":
            node.right = TreeNode(int(tokens[i]))
            queue.append(node.right)
        i += 1
    return root


def sorted_array_to_bst(nums):
    def build(lo, hi):                                   # half-open [lo, hi)
        if lo >= hi:
            return None
        mid = (lo + hi) // 2
        return TreeNode(nums[mid], build(lo, mid), build(mid + 1, hi))

    return build(0, len(nums))

build_tree never slices the lists, so it is O(n) rather than the O(n²) of the version that copies inorder[:mid] at every call. deserialize_levels relies on the string being well-formed, with a marker for every missing child of every real node, which is what serialize_levels writes.

Variations and edge cases

• Inorder plus postorder. Read the postorder list from the back and build the right subtree before the left, as above. Preorder plus postorder alone is ambiguous for nodes with a single child.
• Search tree from preorder alone. Pass an upper bound down and consume values while they are below it; the ordering invariant replaces the inorder list, giving O(n) time with no map.
• Compact serialization. Drop the trailing markers of a level-order string, use a delimiter that cannot appear in values, and encode negative numbers safely. A search tree can be serialized with no markers at all, as plain preorder.
• Sorted linked list to tree. Count the length first, then build the left half recursively while advancing a shared list pointer, so the inorder order matches the list order.
• Edge cases: an empty tree (serialize to a lone marker), a single node, a chain (the recursion depth is n, so mind Python's limit), negative or multi-digit values (split on a delimiter, never on characters), and duplicated values, where the dictionary lookup is no longer valid.

Complexity and tradeoffs

• Time: O(n) for every routine here with a value-to-index dictionary; without it, finding the root in the inorder list makes the build O(n²). Serialization and deserialization are O(n) with 11 tokens for the 5-node example.
• Space: O(n) for the dictionary and the output, plus O(h) recursion depth. The level-order version uses a queue of up to the widest level.
• Baseline. Slicing the arrays at every call gives the same answer but copies O(n) values per call, O(n²) in the worst case. Index bounds and a cursor remove the copying.
• When it fails. Repeated values make two traversals ambiguous, and a single traversal without markers never determines the shape. Very deep trees overflow the recursion limit, so either raise it carefully or convert to the level-order versions, which use a queue and not the call stack.

Problems

The three home problems are the three ideas: rebuild from two traversals, serialize with markers and turn sorted input into a balanced tree. Quad-tree construction is a close cousin with four children; it appears below as "also uses".

Easy

• 108. Convert Sorted Array to Binary Search Tree Grind 169
  Make the middle element the root and build each half recursively, so the two sides never differ in height by more than one.

Medium

• 105. Construct Binary Tree from Preorder and Inorder Traversal Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The first preorder value is the root, and its position in the inorder list splits everything else into the left and right subtrees.

Hard

• 297. Serialize and Deserialize Binary Tree Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Write a preorder traversal with markers for empty children, and read it back in the same order with a shared cursor.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 427. Construct Quad Tree Medium

Connections

This page runs the traversals of the depth-first page backwards and uses the breadth-first page's queue for the level-order encoding. The balanced build is the binary search tree page's invariant used constructively. The same "split by a known position and recurse on both sides" shape appears in divide and conquer, merge sort and segment tree construction later in the roadmap.

Check yourself

References

• Knuth, The Art of Computer Programming, volume 1, section 2.3.1: binary tree traversals and the exercises on reconstructing a tree from two orders.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 12.1 (tree walks) and the exercises on building a tree from a traversal.
• Sedgewick and Wayne, Algorithms, section 3.2: level-order traversal and tree construction.
• Skiena, The Algorithm Design Manual, the divide-and-conquer chapter, for the "split at a known position" argument.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.