‹ DS&A interview · Socratic
DSA · Trees · #53

Construct Binary Tree from Inorder and Postorder Traversal

Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke

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, reconstruct and return the root of the tree. Each node is `{ val, left, right }` with `left`/`right` defaulting to `null`. Implement the function `buildTree(inorder, postorder)`. All values in the tree are unique.

Examples
  • inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] → [3,9,20,null,null,15,7] — The last element of postorder (3) is the root; it splits inorder into left [9] and right [15,20,7].
  • inorder = [-1], postorder = [-1] → [-1] — A single node is its own root with no children.
  • inorder = [2,1], postorder = [2,1] → [1,2,null] — Root 1 has left child 2 and no right child.
Constraints
  • · 1 <= inorder.length <= 3000
  • · postorder.length == inorder.length
  • · -3000 <= inorder[i], postorder[i] <= 3000
  • · inorder and postorder consist of unique values.
  • · Each value of postorder also appears in inorder.
  • · inorder and postorder are guaranteed to be valid traversals of the same binary tree.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.