Construct Binary Tree from Inorder and Postorder Traversal

Medium
1908.

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal is a medium coding problem on arrays, hash table and trees, asked in Amazon, Google and Microsoft interviews.

You are given two integer arrays: inorder, the inorder traversal of a binary tree (left subtree, node, right subtree), and postorder, the postorder traversal of the same tree (left subtree, right subtree, node). All values are distinct.

Rebuild the tree and return its root.

Example 1

Input
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output
[3,9,20,null,null,15,7]
Explanation
3 comes last in postorder, so it is the root; in the inorder list 9 is to its left and 15, 20, 7 to its right. Repeating the split on each side gives the tree.

Example 2

Input
inorder = [-1], postorder = [-1]
Output
[-1]
Explanation
A single node.

Example 3

Input
inorder = [1,2,3], postorder = [3,2,1]
Output
[1,null,2,null,3]
Explanation
Every value sits right of its parent in the inorder list, so the tree is a chain of right children.

Constraints

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • all values are distinct
  • every value of postorder appears in inorder
  • the two arrays describe the same tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Construct Binary Tree from Inorder and Postorder Traversal Solution

Construct Binary Tree from Inorder and Postorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Construct Binary Tree from Inorder and Postorder Traversal is a medium coding problem on arrays, hash table and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given two integer arrays: inorder, the inorder traversal of a binary tree (left subtree, node, right subtree), and postorder, the postorder traversal of the same tree (left subtree, right subtree, node). All values are distinct.

Rebuild the tree and return its root.

Example 1

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Explanation: 3 comes last in postorder, so it is the root; in the inorder list 9 is to its left and 15, 20, 7 to its right. Repeating the split on each side gives the tree.

Example 2

Input: inorder = [-1], postorder = [-1]
Output: [-1]
Explanation: A single node.

Example 3

Input: inorder = [1,2,3], postorder = [3,2,1]
Output: [1,null,2,null,3]
Explanation: Every value sits right of its parent in the inorder list, so the tree is a chain of right children.

Constraints

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • all values are distinct
  • every value of postorder appears in inorder
  • the two arrays describe the same tree

Hints for Construct Binary Tree from Inorder and Postorder Traversal

  1. Hint 1

    The last value of a postorder traversal is always the root.

  2. Hint 2

    Find the root in the inorder list: everything to its left is the left subtree, everything to its right the right subtree.

  3. Hint 3

    Walk postorder from the back with one shared pointer. Read backwards it lists node, right subtree, left subtree — so build the right subtree before the left. Look positions up in a hash map.

How to solve Construct Binary Tree from Inorder and Postorder Traversal

Postorder read from the end names each subtree's root first, then its right subtree, then its left; inorder says which values lie on each side of a root. Consuming postorder backwards while splitting inorder ranges rebuilds the tree.

Approach

  1. Map every value to its index in inorder.
  2. Keep a pointer pos into postorder, starting at its last index.
  3. To build the subtree whose values occupy inorder[lo..hi]: if lo > hi return null; otherwise take postorder[pos] as the root and move pos one step left.
  4. Let mid be the root's index in inorder; build the right subtree from [mid + 1, hi] first, then the left subtree from [lo, mid - 1].
  5. Return the root built for the whole range.

Why it works

Postorder is left subtree, right subtree, node; reversed it is node, right subtree, left subtree — the mirror of preorder. Building the right subtree completely before the left therefore makes the backwards pointer meet exactly the roots the recursion needs, and the inorder position of each root splits its range correctly because values are distinct.

Complexity

  • Time — O(n)
  • Space — O(n) for the map, O(h) for the recursion

Pitfalls

  • Building the left subtree first, as in the preorder version, pairs the wrong roots with the ranges.
  • Searching for the root in inorder each time makes it O(n^2) on a chain.

Reference solution

Python

from typing import List, Optional

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    index = {v: i for i, v in enumerate(inorder)}
    pos = len(postorder) - 1

    def build(lo, hi):
        nonlocal pos
        if lo > hi:
            return None
        v = postorder[pos]
        pos -= 1
        node = TreeNode(v)
        mid = index[v]
        node.right = build(mid + 1, hi)
        node.left = build(lo, mid - 1)
        return node

    return build(0, len(inorder) - 1)

Java

public static TreeNode buildTree(int[] inorder, int[] postorder) {
    Map<Integer, Integer> index = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) index.put(inorder[i], i);
    int[] pos = {postorder.length - 1};
    return build(postorder, index, pos, 0, inorder.length - 1);
}

static TreeNode build(int[] postorder, Map<Integer, Integer> index, int[] pos, int lo, int hi) {
    if (lo > hi) return null;
    int v = postorder[pos[0]--];
    TreeNode node = new TreeNode(v);
    int mid = index.get(v);
    node.right = build(postorder, index, pos, mid + 1, hi);
    node.left = build(postorder, index, pos, lo, mid - 1);
    return node;
}

C++

TreeNode* buildRange(vector<int>& postorder, unordered_map<int, int>& index, int& pos, int lo, int hi);

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    unordered_map<int, int> index;
    for (int i = 0; i < (int) inorder.size(); i++) index[inorder[i]] = i;
    int pos = (int) postorder.size() - 1;
    return buildRange(postorder, index, pos, 0, (int) inorder.size() - 1);
}

TreeNode* buildRange(vector<int>& postorder, unordered_map<int, int>& index, int& pos, int lo, int hi) {
    if (lo > hi) return nullptr;
    int v = postorder[pos--];
    TreeNode* node = new TreeNode(v);
    int mid = index[v];
    node->right = buildRange(postorder, index, pos, mid + 1, hi);
    node->left = buildRange(postorder, index, pos, lo, mid - 1);
    return node;
}

JavaScript

var buildTree = function(inorder, postorder) {
    var index = new Map(), pos = postorder.length - 1;
    for (var i = 0; i < inorder.length; i++) index.set(inorder[i], i);
    function build(lo, hi) {
        if (lo > hi) return null;
        var v = postorder[pos--];
        var node = new TreeNode(v);
        var mid = index.get(v);
        node.right = build(mid + 1, hi);
        node.left = build(lo, mid - 1);
        return node;
    }
    return build(0, inorder.length - 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets