← Create New Paste

Construct Binary Tree From Preorder and Inorder Traversal: A Clear Interview Walkthrough

3 views
This problem (LeetCode 105) gives you two arrays, the preorder and inorder traversals of a binary tree with unique values, and asks you to rebuild the tree. It tests whether you really understand what each traversal order means, and whether you can turn that understanding into clean recursion with index bookkeeping. The two facts you need 1. In preorder (root, left, right), the first element is always the root of the current subtree. 2. In inorder (left, root, right), everything to the left of the root's position belongs to the left subtree, and everything to the right belongs to the right subtree. Say these out loud before coding. Then combine them: take the root from preorder, find it in inorder, and the position tells you how many nodes are in the left subtree. Worked example preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]. The root is 3. In inorder, 3 is at index 1, so the left subtree has one node ([9]) and the right subtree has three ([15, 20, 7]). In preorder, after the root, the next one element is the left subtree ([9]) and the remaining three are the right subtree ([20, 15, 7]). Recurse: the right subtree's root is 20, with 15 on its left and 7 on its right. The naive version and why it's slow A direct implementation slices arrays at every level and uses a linear search to find the root in inorder. Slicing copies data and the search is O(n), so the worst case (a skewed tree) is O(n^2). It's fine to mention this as a first step. The optimized version Precompute a hash map from value to its inorder index, so finding the root is O(1). Then avoid slicing by passing index boundaries instead of arrays. A neat approach keeps a single pointer into preorder that advances each time you create a node, and the recursive function takes only the inorder range (left, right): - If left > right, return null. - Take preorder[pointer] as the root value and advance the pointer. - Look up its inorder index mid. - Build the left subtree from (left, mid - 1), then the right subtree from (mid + 1, right). Building left before right matters, because that is the order in which preorder lists the nodes. This gives O(n) time and O(n) space for the map and recursion stack. Edge cases and follow-ups - Empty arrays should return null. - Unique values are required; with duplicates the tree isn't uniquely determined, which is a good point to raise. - A common follow-up is building from inorder and postorder. There, the root is the last element of postorder, and you build the right subtree before the left. - Preorder plus postorder alone cannot uniquely determine a general binary tree, which is a nice detail to know. Presenting it well Draw the example, show how the inorder split determines subtree sizes, and then code the index version. Trace one recursive call to show the pointer advancing correctly. If you want support staying calm and organized while explaining, Linkjob AI (https://linkjob.ai) offers real-time help during live job interviews and technical interviews.
Created Nov 17, 2026 15:02 Expires Nov 17, 2027 15:02