Practice › Trees
Construct Tree from Preorder and Inorder
Medium · Trees · Asked at Amazon, Microsoft, Google, Bloomberg
Rebuild the binary tree from its preorder and inorder traversals (all values distinct) and print its postorder traversal.
Input
First line: n. Second line: the preorder traversal. Third line: the inorder traversal.
Output
The postorder traversal, space-separated.
Constraints
- 1 ≤ n ≤ 3000
- Values are distinct
The first preorder value is the root; its position in the inorder sequence splits left and right subtrees. A hash map from value to inorder index makes each split O(1).
Example 1
Input
5 3 9 20 15 7 9 3 15 20 7
Output
9 15 7 20 3
Example 2
Input
1 -5 -5
Output
-5
Hints
- preorder[0] is the root. Find it in the inorder sequence: everything before it is the left subtree, everything after is the right subtree.
- The left subtree has k nodes, so it occupies the next k entries of the preorder too. Recurse; a hash map value → inorder index makes the lookup O(1).
Approach
build(preStart, inStart, len): the root is pre[preStart]; its inorder position pos gives k = pos − inStart left-subtree nodes. Recurse on (preStart + 1, inStart, k) for the left and (preStart + 1 + k, pos + 1, len − k − 1) for the right. Since only the postorder is needed, we can print in postorder directly from the recursion (left, right, then root) without allocating nodes — though building them works the same way.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
vector<long long> pre, ino, out;
unordered_map<long long, int> pos;
void build(int ps, int is, int len) {
if (len <= 0) return;
long long root = pre[ps];
int k = pos[root] - is;
build(ps + 1, is, k);
build(ps + 1 + k, is + k + 1, len - k - 1);
out.push_back(root);
}
int main() {
int n;
cin >> n;
pre.resize(n);
ino.resize(n);
for (auto &x : pre) cin >> x;
for (int i = 0; i < n; i++) {
cin >> ino[i];
pos[ino[i]] = i;
}
build(0, 0, n);
for (int i = 0; i < n; i++) cout << out[i] << (i + 1 < n ? " " : "\n");
return 0;
}Python solution
import sys
sys.setrecursionlimit(100000)
data = list(map(int, sys.stdin.read().split()))
n = data[0]
pre, ino = data[1 : 1 + n], data[1 + n : 1 + 2 * n]
pos = {v: i for i, v in enumerate(ino)}
out = []
def build(ps, is_, length):
if length <= 0:
return
root = pre[ps]
k = pos[root] - is_
build(ps + 1, is_, k)
build(ps + 1 + k, is_ + k + 1, length - k - 1)
out.append(root)
build(0, 0, n)
print(*out)Java solution
import java.util.*;
public class Main {
static long[] pre;
static Map<Long, Integer> pos = new HashMap<>();
static StringBuilder sb = new StringBuilder();
static void build(int ps, int is, int len) {
if (len <= 0) return;
long root = pre[ps];
int k = pos.get(root) - is;
build(ps + 1, is, k);
build(ps + 1 + k, is + k + 1, len - k - 1);
sb.append(sb.length() > 0 ? " " : "").append(root);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
pre = new long[n];
for (int i = 0; i < n; i++) pre[i] = sc.nextLong();
for (int i = 0; i < n; i++) pos.put(sc.nextLong(), i);
build(0, 0, n);
System.out.println(sb);
}
}Solve Construct Tree from Preorder and Inorder online · All practice problems