Building and serialising binary trees

Building a binary tree back from a list of its keys works only when the list keeps enough of the shape. One traversal on its own does not: the preorder A B fits a tree in which B is A’s left child and one in which it is the right child. With distinct keys, preorder and inorder together fix the tree. The first preorder key is the root, and its place in the inorder list says which keys lie to its left and which to its right, so the same step repeats on each side. Serialising binary trees for a file, a database or a test case takes another route: one traversal, with a marker for every empty child place, so the text records the shape itself. This lesson rebuilds a family tree from its two lists, writes trees out with markers and reads them back, and checks 1,000 random round trips.

Why one traversal is not enough

A traversal lists every key but drops the positions of the empty child places. Take the keys of a preorder and place them, in order, into any binary tree shape with that many nodes: every shape produces the same preorder. Three keys therefore fit 5 different trees, and eight keys fit 1,430, the number of binary tree shapes with eight nodes. Something has to put the lost information back, either a second traversal that fixes left and right, or markers that record each empty place where it occurs.

Building a tree from preorder and inorder

1. The first key of the preorder is the root.
2. Find it in the inorder: the keys before it form the left subtree and the keys after it the right subtree.
3. If the left subtree has k keys, the next k keys of the preorder are its preorder, and the rest belong to the right subtree.
4. Repeat the same steps on each side until no keys are left.

The program below follows these steps for a family of eight. A dictionary gives each key’s position in the inorder list, so finding a root costs O(1), and a counter remembers how many preorder keys have become nodes:

"""A family tree rebuilt from its preorder and inorder lists, traced, printed and walked in postorder."""

preorder = ["Asha", "Bina", "Chetan", "Dev", "Hari", "Esha", "Farid", "Gita"]
inorder = ["Chetan", "Bina", "Dev", "Hari", "Asha", "Farid", "Esha", "Gita"]


class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None


def rebuild(preorder, inorder, trace=None):
    where = {key: i for i, key in enumerate(inorder)}     # each key's position in the inorder list
    if len(where) != len(inorder) or sorted(preorder) != sorted(inorder):
        raise ValueError("the two lists must hold the same distinct keys")
    taken = 0                                              # how many preorder keys have become nodes

    def build(lo, hi):
        """The subtree whose keys are inorder[lo:hi]; its root is the next unused preorder key."""
        nonlocal taken
        if lo == hi:
            return None
        node = Node(preorder[taken])
        taken += 1
        mid = where[node.key]
        if trace is not None:
            trace.append(f"{node.key:<7} left: {' '.join(inorder[lo:mid]) or '-':<22} right: {' '.join(inorder[mid + 1:hi]) or '-'}")
        node.left = build(lo, mid)
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(inorder))


def show(node, prefix=""):
    """Prints the tree sideways: each child under its parent, marked L or R."""
    for side, child in (("L", node.left), ("R", node.right)):
        if child:
            print(f"{prefix}{side} {child.key}")
            show(child, prefix + "  ")


def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.key)
    return out


steps = []
root = rebuild(preorder, inorder, steps)
print("\n".join(steps))
print(root.key)
show(root)
print("postorder:", " ".join(postorder(root, [])))

Asha    left: Chetan Bina Dev Hari   right: Farid Esha Gita
Bina    left: Chetan                 right: Dev Hari
Chetan  left: -                      right: -
Dev     left: -                      right: Hari
Hari    left: -                      right: -
Esha    left: Farid                  right: Gita
Farid   left: -                      right: -
Gita    left: -                      right: -
Asha
L Bina
  L Chetan
  R Dev
    R Hari
R Esha
  L Farid
  R Gita
postorder: Chetan Hari Dev Bina Farid Gita Esha Asha

The trace shows each split. Asha divides the inorder into four keys on the left and three on the right; Bina, the next preorder key, divides the left four into Chetan and Dev with Hari, and so on until every key has its place. Building the tree this way handles each key once, so with the dictionary it takes O(n) time. Searching the inorder list for every root instead would take O(n²) steps on a path. The recursion goes as deep as the tree is tall.

Serialising binary trees with markers

Serialising binary trees needs no second list if the text marks every empty place. The usual way is preorder with a marker such as # wherever a child is missing: a tree of n keys becomes n keys and n + 1 markers, and a reader rebuilds it by taking tokens in order, making a node for a key and an empty place for a marker. Here the family tree goes out and comes back, followed by the level-order list form that many test-case formats use, and 1,000 random trees make the same round trip:

"""Preorder with a marker for every empty place: write a tree out, read it back, and check 1,000 random round trips."""
import random
from collections import deque


class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right


def serialise(root):
    """Preorder, with '#' for each empty child place: n keys and n + 1 markers."""
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        if node is None:
            out.append("#")
        else:
            out.append(str(node.key))
            stack += [node.right, node.left]      # the left subtree is written first
    return " ".join(out)


def deserialise(text):
    tokens = iter(text.split())

    def read():
        token = next(tokens)                       # StopIteration here means the text was cut short
        if token == "#":
            return None
        node = Node(token)
        node.left = read()
        node.right = read()
        return node

    root = read()
    if next(tokens, None) is not None:
        raise ValueError("text left over after the tree")
    return root


def level_order_format(root):
    """The common list form: level order with 'null' for empty places, trailing nulls dropped."""
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        out.append("null" if node is None else str(node.key))
        if node is not None:
            queue += [node.left, node.right]
    while out and out[-1] == "null":
        out.pop()
    return "[" + ",".join(out) + "]"


family = Node("Asha", Node("Bina", Node("Chetan"), Node("Dev", None, Node("Hari"))),
              Node("Esha", Node("Farid"), Node("Gita")))
text = serialise(family)
print(text)
print(f"{len(text.split())} tokens: 8 keys and {text.split().count('#')} markers")
print(level_order_format(family))
print("read back and written again:", serialise(deserialise(text)) == text)


def random_tree(n, rng):
    if n == 0:
        return None
    root = Node(0)
    places = [(root, "left"), (root, "right")]
    for k in range(1, n):
        parent, side = places.pop(rng.randrange(len(places)))
        child = Node(k)
        setattr(parent, side, child)
        places += [(child, "left"), (child, "right")]
    return root


rng = random.Random(11)
failures = 0
for _ in range(1000):
    t = random_tree(rng.randint(0, 60), rng)
    s = serialise(t)
    failures += serialise(deserialise(s)) != s
print("1,000 random trees of 0 to 60 nodes, serialised, read back and serialised again; differences:", failures)

Asha Bina Chetan # # Dev # Hari # # Esha Farid # # Gita # #
17 tokens: 8 keys and 9 markers
[Asha,Bina,Esha,Chetan,Dev,Farid,Gita,null,null,null,Hari]
read back and written again: True
1,000 random trees of 0 to 60 nodes, serialised, read back and serialised again; differences: 0

The family tree becomes 17 tokens, 8 keys and 9 markers, and reading it back gives a tree that writes out as exactly the same text. None of the 1,000 random trees, from empty up to 60 nodes, changed on the way. The level-order form writes the tree level by level with null for empty places and leaves out the markers at the end.

The choices compared in depth

Preorder with postorder fixes a tree only when no node has exactly one child. Postorder with inorder, or level order with inorder, fixes a tree just as preorder with inorder does. A rebuild driven by an explicit stack handles a 100,000-node path that the recursive version cannot. And the two text formats differ in size: level order is shorter for complete trees, preorder for deep or sparse ones.

Exercise: postorder from two orders

The exercise gives the preorder and inorder of a tree and asks for its postorder, on the family tree, on paths of 900 nodes and on a random tree of 3,000.

def postorder_from(preorder, inorder):
    """The postorder of the binary tree with these preorder and inorder lists (distinct keys)."""
    raise NotImplementedError("write postorder_from")

import random

from two_orders import postorder_from


def orders_of(n, seed):
    """Preorder, inorder and postorder of a random binary tree with keys 0 to n - 1, built without deep recursion."""
    rng = random.Random(seed)
    left, right = [None] * n, [None] * n
    places = [(0, "L"), (0, "R")]
    for k in range(1, n):
        p, side = places.pop(rng.randrange(len(places)))
        (left if side == "L" else right)[p] = k
        places += [(k, "L"), (k, "R")]
    pre, ino, post = [], [], []
    stack = [(0, False)]
    while stack:
        v, done = stack.pop()
        if done:
            post.append(v)
            continue
        pre.append(v)
        stack.append((v, True))
        if right[v] is not None:
            stack.append((right[v], False))
        if left[v] is not None:
            stack.append((left[v], False))
    # inorder: a second walk
    stack, v = [], 0
    while stack or v is not None:
        while v is not None:
            stack.append(v)
            v = left[v]
        v = stack.pop()
        ino.append(v)
        v = right[v]
    return pre, ino, post


def test_empty_tree():
    """an empty tree has an empty postorder"""
    assert postorder_from([], []) == []


def test_single_key():
    """one key is its own postorder"""
    assert postorder_from(["Asha"], ["Asha"]) == ["Asha"]


def test_family_tree():
    """the lesson's family tree"""
    pre = ["Asha", "Bina", "Chetan", "Dev", "Hari", "Esha", "Farid", "Gita"]
    ino = ["Chetan", "Bina", "Dev", "Hari", "Asha", "Farid", "Esha", "Gita"]
    assert postorder_from(pre, ino) == ["Chetan", "Hari", "Dev", "Bina", "Farid", "Gita", "Esha", "Asha"]


def test_left_and_right_paths():
    """paths of 900 nodes: leaning left the inorder is reversed, leaning right it equals the preorder"""
    pre = list(range(900))
    assert postorder_from(pre, pre[::-1]) == pre[::-1]
    assert postorder_from(pre, list(pre)) == pre[::-1]


def test_random_tree():
    """a random tree of 3,000 nodes"""
    pre, ino, post = orders_of(3_000, seed=4)
    assert postorder_from(pre, ino) == post

/** The postorder of the binary tree with these preorder and inorder lists (distinct keys). */
export function postorderFrom(preorder, inorder) {
  throw new Error('write postorderFrom');
}

import { test, assert } from 'mysmartcopilot:test';
import { postorderFrom } from './two_orders.mjs';

// Preorder, inorder and postorder of a random binary tree with keys 0 to n - 1 (a small fixed generator, no recursion).
function ordersOf(n, seed) {
  let s = seed;
  const next = (m) => { s = (s * 1103515245 + 12345) % 2147483648; return s % m; };
  const left = new Array(n).fill(null);
  const right = new Array(n).fill(null);
  const places = [[0, 'L'], [0, 'R']];
  for (let k = 1; k < n; k++) {
    const [p, side] = places.splice(next(places.length), 1)[0];
    (side === 'L' ? left : right)[p] = k;
    places.push([k, 'L'], [k, 'R']);
  }
  const pre = [], ino = [], post = [];
  const stack = [[0, false]];
  while (stack.length) {
    const [v, done] = stack.pop();
    if (done) { post.push(v); continue; }
    pre.push(v);
    stack.push([v, true]);
    if (right[v] !== null) stack.push([right[v], false]);
    if (left[v] !== null) stack.push([left[v], false]);
  }
  const st = [];
  let v = 0;
  while (st.length || v !== null) {
    while (v !== null) { st.push(v); v = left[v]; }
    v = st.pop();
    ino.push(v);
    v = right[v];
  }
  return { pre, ino, post };
}

test('an empty tree has an empty postorder', () => {
  assert.deepEqual(postorderFrom([], []), []);
});

test('one key is its own postorder', () => {
  assert.deepEqual(postorderFrom(['Asha'], ['Asha']), ['Asha']);
});

test("the lesson's family tree", () => {
  const pre = ['Asha', 'Bina', 'Chetan', 'Dev', 'Hari', 'Esha', 'Farid', 'Gita'];
  const ino = ['Chetan', 'Bina', 'Dev', 'Hari', 'Asha', 'Farid', 'Esha', 'Gita'];
  assert.deepEqual(postorderFrom(pre, ino), ['Chetan', 'Hari', 'Dev', 'Bina', 'Farid', 'Gita', 'Esha', 'Asha']);
});

test('paths of 900 nodes: leaning left the inorder is reversed, leaning right it equals the preorder', () => {
  const pre = Array.from({ length: 900 }, (_, i) => i);
  const reversed = [...pre].reverse();
  assert.deepEqual(postorderFrom(pre, reversed), reversed);
  assert.deepEqual(postorderFrom(pre, [...pre]), reversed);
});

test('a random tree of 3,000 nodes', () => {
  const { pre, ino, post } = ordersOf(3000, 4);
  assert.deepEqual(postorderFrom(pre, ino), post);
});

Which traversal pairs determine a tree: proofs, counterexamples and every shape checked Pro: opens with a Pro, Premium or Ultimate pass

Linear-time and stack-safe rebuilding, measured on 100,000 nodes Pro: opens with a Pro, Premium or Ultimate pass

Formats compared, parsing untrusted text safely, and five languages Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• One traversal loses the empty places, so it fits every shape with that many nodes.
• With distinct keys, preorder and inorder fix a tree: the first preorder key is the root, and its inorder position splits the rest.
• A dictionary of inorder positions makes the rebuild O(n); scanning for each root is O(n²) on a path.
• Preorder with a marker for every empty place records the shape by itself: n keys, n + 1 markers, and a round trip that gives back the same text.