Skip to main content

77. Construct Binary Tree from Inorder and Postorder Traversal

mediumAsked at Ola

Rebuild a binary tree from its inorder and postorder traversals.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Constraints

  • 1 <= inorder.length <= 3000
  • inorder.length == postorder.length
  • All values are unique

Examples

Example 1

Input
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output
[3,9,20,null,null,15,7]

Example 2

Input
inorder = [-1], postorder = [-1]
Output
[-1]

Approaches

1. Slice and search

postorder.pop is root; split inorder around it; recurse right first.

Time
O(n^2)
Space
O(n^2)
// slicing approach; quadratic

Tradeoff:

2. Index map with right-first DFS

Map inorder values to indices; pop from postorder end; recurse right then left because postorder visits right before root.

Time
O(n)
Space
O(n)
function buildTree(inorder, postorder) {
  const idx = new Map(inorder.map((v, i) => [v, i]));
  let p = postorder.length - 1;
  const go = (lo, hi) => {
    if (lo > hi) return null;
    const v = postorder[p--];
    const i = idx.get(v);
    const node = { val: v, left: null, right: null };
    node.right = go(i+1, hi);
    node.left = go(lo, i-1);
    return node;
  };
  return go(0, inorder.length - 1);
}

Tradeoff:

Ola-specific tips

Ola interviewers want you to explain why you must recurse right before left; tie it to consuming a postorder dispatch log from the latest event back to root.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Construct Binary Tree from Inorder and Postorder Traversal and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →