DSA interview question

Construct a Binary Tree from Preorder and Inorder Traversals

Hard · Data structures · Topics: tree, hash map, recursion

The problem

The backup tool from before stored each tree as its preorder and inorder sequences (values are distinct), and now it must rebuild the tree. Preorder's first value is the root. Finding that value in inorder splits the rest: everything to its left forms the left subtree, and everything to its right the right subtree. Those slices, plus the next preorder values, rebuild each subtree recursively. A hash map from value to inorder index makes each split O(1).

Example: preorder [3, 9, 20, 15, 7], inorder [9, 3, 15, 20, 7] → [3, 9, 20, null, null, 15, 7].

Function signature

TreeNode* buildTree(const vector<int>& preorder, const vector<int>& inorder);

Test cases

Input `(preorder, inorder)`	Output (level order)	Explanation
`([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])`	`[3, 9, 20, null, null, 15, 7]`
`([1, 2, 4, 5, 3, 6, 7], [4, 2, 5, 1, 6, 3, 7])`	`[1, 2, 3, 4, 5, 6, 7]`	A perfect tree
`([1, 2], [2, 1])`	`[1, 2]`	2 is a left child
`([1, 2], [1, 2])`	`[1, null, 2]`	2 is a right child
`([-1], [-1])`	`[-1]`

(Confirm: values are distinct; both arrays describe the same tree; the output is shown in LeetCode's level-order format.)

How interviewers phrase it

"Given two integer arrays preorder and inorder of the same binary tree, construct and return the tree" (LeetCode 105).

Clarifying questions to ask

Are values unique? (Yes, which makes the inorder lookup unambiguous.)
Are the inputs guaranteed consistent? (Yes.)
How large is n? (Up to 3000, so the naive O(n²) search works but a map is expected.)

Follow-ups to expect

"Why the hash map?"
"How do you know how many preorder elements belong to the left subtree?"
"Why build the left subtree before the right?"
"Postorder + inorder?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview