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

Construct Binary Tree from Preorder and Inorder Traversal

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

Given two integer arrays `preorder` and `inorder` representing the preorder and inorder traversal of a binary tree, reconstruct and return the **root** of the tree. All values in the tree are **unique**. Each tree node has the shape `{ val, left, right }`, where `left` and `right` are child nodes or `null`. Implement the function `buildTree(preorder, inorder)`.

Examples
  • preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] → [3,9,20,null,null,15,7] — 3 is the root; 9 is its left subtree; 20 (with children 15 and 7) is its right subtree.
  • preorder = [-1], inorder = [-1] → [-1] — A single-node tree.
  • preorder = [1,2], inorder = [2,1] → [1,2] — 2 is the left child of root 1.
Constraints
  • · 1 <= preorder.length <= 3000
  • · inorder.length === preorder.length
  • · -3000 <= preorder[i], inorder[i] <= 3000
  • · preorder and inorder consist of unique values
  • · inorder is a valid inorder traversal of the same tree described by preorder
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.