Construct Binary Tree from Preorder and Inorder

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two integer arrays, preorder and inorder, which are the preorder and inorder traversals of the same binary tree. All node values are **distinct**, so exactly one tree matches both traversals. Rebuild that tree and return its root. The tree is graded by its level-order serialization (for example [3,9,20,null,null,15,7]). Aim for O(n) time: the first value of preorder is always the root, and its position in inorder splits the remaining values into the left and right subtrees.

Examples

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
3 is the root; 9 is left of it in inorder, and 15,20,7 form the right subtree rooted at 20.
Input: preorder = [-1], inorder = [-1]
Output: [-1]
A single node.

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • All values are distinct
  • Both arrays describe the same binary tree

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems