DSA Building a Tree from Traversals

The problem

Building a tree from traversals rebuilds one binary tree from its preorder and inorder lists. Preorder visits a node before its children. Inorder visits a node's left subtree, then the node, then its right subtree.

The values in the tree are unique. That condition is what makes one answer possible. Each case below gives both lists and the postorder list the rebuilt tree must produce.

cases = [
    ([5, 3, 1, 4, 8, 7, 9], [1, 3, 4, 5, 7, 8, 9], [1, 4, 3, 7, 9, 8, 5]),
    ([5, 3, 8], [3, 5, 8], [3, 8, 5]),
    ([7], [7], [7]),
    ([3, 2, 1], [1, 2, 3], [1, 2, 3]),
]
for preorder, inorder, postorder in cases:
    print("preorder:", preorder, "inorder:", inorder, "postorder of rebuilt tree:", postorder)

Postorder is the check, not an input. A rebuilt tree is right when all three of its walks match. Matching only preorder would prove almost nothing, since many trees share one preorder list.

Intuition: preorder names the root, inorder splits around it

The first preorder value is always the next root. Nothing is visited before the root in preorder. The root's position in inorder then splits the remaining values into two groups.

Every value before the root in inorder belongs to its left subtree. Every value after it belongs to its right subtree. The same two steps then repeat inside each group.

preorder = [5, 3, 1, 4, 8, 7, 9]
inorder = [1, 3, 4, 5, 7, 8, 9]
root_value = preorder[0]
split = inorder.index(root_value)
print("root:", root_value)
print("left inorder:", inorder[:split])
print("right inorder:", inorder[split + 1:])
print("next root, first unseen preorder value after the left part:", preorder[1])

The root is 5, and its split leaves three values on each side. The left subtree therefore holds exactly three nodes. Preorder values are consumed in matching blocks as the build descends.

Brute force: scan and slice for every split

The brute force finds each root's inorder position by scanning the list from the start. It then slices both lists into left and right pieces. Each slice copies its values into a new list.

The method works and its logic is easy to check. Its cost sits in the scans. A counter records every inorder position examined while searching for roots.

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

def build_brute(preorder, inorder, scans):
    if not preorder:
        return None
    value = preorder[0]
    split = 0
    for index, item in enumerate(inorder):
        scans[0] += 1
        if item == value:
            split = index
            break
    node = TreeNode(value)
    left_size = split
    node.left = build_brute(preorder[1:1 + left_size], inorder[:split], scans)
    node.right = build_brute(preorder[1 + left_size:], inorder[split + 1:], scans)
    return node

def postorder(node, order):
    if node is None:
        return
    postorder(node.left, order)
    postorder(node.right, order)
    order.append(node.value)

preorder = [5, 3, 1, 4, 8, 7, 9]
inorder = [1, 3, 4, 5, 7, 8, 9]
scans = [0]
root = build_brute(preorder, inorder, scans)
order = []
postorder(root, order)
print("rebuilt postorder:", order)
print("inorder positions scanned:", scans[0])
print("nodes built:", len(order))

Seven nodes already cost more position scans than nodes. A root sitting late in its inorder range is found late every time. The copying slices add further work on top of the scans.

The optimal solution: an index map and ranges, no copies

An index map is a dict that stores the inorder position of each value, and reading each split from that map while passing ranges instead of slices builds the tree in one step per node. That one sentence is the whole method.

A range is a pair of low and high inorder indexes. The build moves a shared preorder index forward as it creates nodes. No list is scanned and no list is copied after the map is built.

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

def build(preorder, index_map, pre_index, low, high, built):
    if low > high:
        return None
    value = preorder[pre_index[0]]
    pre_index[0] += 1
    built[0] += 1
    node = TreeNode(value)
    split = index_map[value]
    node.left = build(preorder, index_map, pre_index, low, split - 1, built)
    node.right = build(preorder, index_map, pre_index, split + 1, high, built)
    return node

def walk(node, order, kind):
    if node is None:
        return
    if kind == "pre":
        order.append(node.value)
    walk(node.left, order, kind)
    if kind == "in":
        order.append(node.value)
    walk(node.right, order, kind)
    if kind == "post":
        order.append(node.value)

def rebuild(preorder, inorder):
    index_map = {value: index for index, value in enumerate(inorder)}
    built = [0]
    root = build(preorder, index_map, [0], 0, len(inorder) - 1, built)
    return root, built[0]

cases = [
    ([5, 3, 1, 4, 8, 7, 9], [1, 3, 4, 5, 7, 8, 9], [1, 4, 3, 7, 9, 8, 5]),
    ([5, 3, 8], [3, 5, 8], [3, 8, 5]),
    ([7], [7], [7]),
    ([3, 2, 1], [1, 2, 3], [1, 2, 3]),
]
for preorder, inorder, expected_post in cases:
    root, built = rebuild(preorder, inorder)
    pre, ino, post = [], [], []
    walk(root, pre, "pre")
    walk(root, ino, "in")
    walk(root, post, "post")
    print("postorder:", post, "match:", post == expected_post,
          "preorder match:", pre == preorder, "inorder match:", ino == inorder,
          "nodes built:", built)

All four cases from the start of the article pass on all three walks. The node count equals the list length each time. Each value becomes a node exactly once.

Walkthrough: building [5, 3, 8] from [3, 5, 8]

The walkthrough builds the small case with a traced copy of the optimal build. Each line prints one root choice. The line shows the inorder range that root governs and the two ranges it creates.

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

def build_traced(preorder, index_map, pre_index, low, high, depth):
    if low > high:
        print("  " * depth + "empty range", low, "to", high, "- return None")
        return None
    value = preorder[pre_index[0]]
    pre_index[0] += 1
    split = index_map[value]
    print("  " * depth + "root", value, "- inorder range", low, "to", high,
          "- left range", low, "to", split - 1, "- right range", split + 1, "to", high)
    node = TreeNode(value)
    node.left = build_traced(preorder, index_map, pre_index, low, split - 1, depth + 1)
    node.right = build_traced(preorder, index_map, pre_index, split + 1, high, depth + 1)
    return node

preorder = [5, 3, 8]
inorder = [3, 5, 8]
index_map = {value: index for index, value in enumerate(inorder)}
root = build_traced(preorder, index_map, [0], 0, len(inorder) - 1, 0)
print("built root:", root.value, "left:", root.left.value, "right:", root.right.value)

The first line makes 5 the root of the full range. Its left range holds only index 0, so 3 becomes its left child. Its right range holds only index 2, so 8 becomes its right child.

Empty ranges print where a child is missing. Node 3 and node 8 each produce two empty ranges. The build ends when every range has been consumed exactly once.

Complexity

The scanning build can scan a whole range for each node, so its worst-case time is O(n^2) for n values. The index map build does one lookup and one node creation per value, so its time is O(n).

The scanning build copies lists at every split, so its extra space can reach O(n^2) across a whole build in the worst case. The index map build stores one map of n entries plus its recursion stack, so its extra space is O(n).

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

def build_brute(preorder, inorder, scans):
    if not preorder:
        return None
    value = preorder[0]
    split = 0
    for index, item in enumerate(inorder):
        scans[0] += 1
        if item == value:
            split = index
            break
    node = TreeNode(value)
    node.left = build_brute(preorder[1:1 + split], inorder[:split], scans)
    node.right = build_brute(preorder[1 + split:], inorder[split + 1:], scans)
    return node

def build_fast(preorder, index_map, pre_index, low, high, lookups):
    if low > high:
        return None
    value = preorder[pre_index[0]]
    pre_index[0] += 1
    lookups[0] += 1
    split = index_map[value]
    node = TreeNode(value)
    node.left = build_fast(preorder, index_map, pre_index, low, split - 1, lookups)
    node.right = build_fast(preorder, index_map, pre_index, split + 1, high, lookups)
    return node

for n in [5, 10, 20]:
    inorder = list(range(1, n + 1))
    preorder = list(range(n, 0, -1))
    scans = [0]
    build_brute(preorder, inorder, scans)
    index_map = {value: index for index, value in enumerate(inorder)}
    lookups = [0]
    build_fast(preorder, index_map, [0], 0, n - 1, lookups)
    print("chain nodes", n, "- brute scans:", scans[0], " map lookups:", lookups[0])

A left chain is the bad shape for scanning, because each root sits at the end of its range. The scan counts grow roughly with the square of the size. The lookup counts equal the node counts exactly.

Edge cases and pitfalls

Two empty lists rebuild to None. One value rebuilds to a single node with two empty children. Chains rebuild correctly in both directions, as the right chain run below shows.

Duplicate values break the method itself. The index map keeps only one position per value, so a list of two copies of 2 gives a map of size 1. No split can then be trusted, and the problem rules duplicates out for this reason.

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

def build(preorder, index_map, pre_index, low, high, built):
    if low > high:
        return None
    value = preorder[pre_index[0]]
    pre_index[0] += 1
    built[0] += 1
    node = TreeNode(value)
    split = index_map[value]
    node.left = build(preorder, index_map, pre_index, low, split - 1, built)
    node.right = build(preorder, index_map, pre_index, split + 1, high, built)
    return node

def walk(node, order, kind):
    if node is None:
        return
    if kind == "pre":
        order.append(node.value)
    walk(node.left, order, kind)
    if kind == "in":
        order.append(node.value)
    walk(node.right, order, kind)
    if kind == "post":
        order.append(node.value)

def rebuild(preorder, inorder):
    index_map = {value: index for index, value in enumerate(inorder)}
    built = [0]
    root = build(preorder, index_map, [0], 0, len(inorder) - 1, built)
    return root, built[0]

root, built = rebuild([], [])
print("empty lists root:", root, "nodes built:", built)
root, built = rebuild([7], [7])
print("single value root:", root.value, "left:", root.left, "right:", root.right)
inorder = [2, 2]
index_map = {value: index for index, value in enumerate(inorder)}
print("duplicate inorder list:", inorder, "index map size:", len(index_map))
root, built = rebuild([1, 2, 3], [1, 2, 3])
order = []
walk(root, order, "post")
print("right chain postorder:", order)

A second pitfall is trusting one walk as the check. Two different trees can share a preorder list. The rebuilt tree earns trust only when its preorder and inorder both match the inputs.