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.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View 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)
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
Node* build_tree(const vector<long long>& preorder, const vector<long long>& inorder) {
// Precondition: valid traversals with the same unique values.
unordered_map<long long, int> index;
for (int i = 0; i < static_cast<int>(inorder.size()); ++i) index[inorder[i]] = i;
int cursor = 0;
function<Node*(int, int)> build = [&](int left, int right) -> Node* {
if (left > right) return nullptr;
long long value = preorder[cursor++];
int mid = index.at(value);
Node* node = new Node(value);
node->left = build(left, mid - 1);
node->right = build(mid + 1, right);
return node;
};
return build(0, static_cast<int>(inorder.size()) - 1);
}