Workspace

Problem workspace

3 day streakD

Build from Preorder & Inorder

MediumTreesConstruction

The challenge

Reconstruct the unique binary tree given its preorder and inorder traversals.

Inputs must be valid traversals of the same tree with unique values. These snippets assume that precondition rather than validating arbitrary arrays.

Example

Preorder [8,4,2,6,12,10,14] and inorder [2,4,6,8,10,12,14] reconstruct the balanced example.

Use the walkthrough below to inspect the input and each state change.

See Build tree, step by step

Follow the branches. Watch the state change.

7 input nodesL = left · R = right
Inspect the input.Labels identify node objects; numbers are their values. Left and right child pointers define the tree. Node labels identify objects; numbers show their values. The pointer table below provides the same structure in text.LRLRLR2D4B6E8A · root10F12C14G
CurrentProcessedPending
View child pointers & node state
Node state · null means no child
NodeValueLeftRightState
A8BC—
B4DE—
C12FG—
D2nullnull—
E6nullnull—
F10nullnull—
G14nullnull—
Step 01 / 17

Inspect the input.

Labels identify node objects; numbers are their values. Left and right child pointers define the tree.

root = A:8
View original input

A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]

Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.

Put it into code

Preorder chooses the root; its inorder position divides the left and right subtrees.

Nodes store value, left, and right. C++ uses C++17 or later.

from collections import deque

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

def build_tree(preorder, inorder):
    # Precondition: valid traversals with the same unique values.
    index = {value: i for i, value in enumerate(inorder)}
    cursor = 0
    def build(left, right):
        nonlocal cursor
        if left > right:
            return None
        value = preorder[cursor]
        cursor += 1
        mid = index[value]
        node = Node(value)
        node.left = build(left, mid - 1)
        node.right = build(mid + 1, right)
        return node
    return build(0, len(inorder) - 1)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap