Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. preorder[0] is the root. Find it in the inorder sequence: everything before it is the left subtree, everything after is the right subtree.
  2. 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