Construct Binary Tree LeetCode 105 Guide

LeetCode 105, Construct Binary Tree from Preorder and Inorder Traversal, gives you two integer arrays: preorder and inorder, each containing the same n unique values representing the nodes of a binary tree. Your task is to reconstruct the binary tree and return its root.

Preorder traversal visits nodes in root-left-right order. Inorder traversal visits them in left-root-right order. Given both traversals, there is exactly one binary tree that produces them — because all values are unique, the traversals together uniquely identify the structure. This problem appears frequently at Google, Facebook, and Amazon.

The problem is medium difficulty and is the foundation for LeetCode 106, which reconstructs a binary tree from postorder and inorder. Mastering LeetCode 105 gives you the mental model for an entire family of tree reconstruction problems.

The core observation is that preorder[0] is always the root of the current subtree. Once you know the root, find its position in the inorder array. Everything to the left of that position in inorder belongs to the left subtree; everything to the right belongs to the right subtree.

The size of the left subtree in inorder tells you how many elements to take from preorder for the left subtree: the next leftSize elements in preorder after the root form the preorder traversal of the left subtree. The remaining elements form the preorder traversal of the right subtree.

This two-array partnership uniquely defines the tree because all values are unique. With duplicates, the reconstruction would be ambiguous — you could not determine which occurrence of a repeated value in inorder corresponds to the root.

The recursive approach pops the first element of the remaining preorder array to use as the current root. It then locates this value in the inorder array to determine the left subtree size. The left subtree is built from the next leftSize elements of preorder and the left portion of inorder. The right subtree is built from the remaining preorder elements and the right portion of inorder.

Each recursive call reduces the problem to a smaller subtree. The base case is when the preorder or inorder subarray is empty, in which case null is returned. The recursion terminates because each call processes at least one node and the subarrays shrink with every level.

Without any optimization, the naive approach slices arrays at each recursive call, which is O(n) per call for the slice operation, resulting in O(n^2) total time for a balanced tree and O(n^2) worst case for a skewed tree.

Searching the inorder array for the root value at each recursive call costs O(n) per call. For a balanced tree with O(log n) levels, this yields O(n log n) total — but for a skewed tree (like a linked list), every call searches an array of size proportional to the remaining nodes, giving O(n^2) total.

The fix is to precompute a hashmap from value to inorder index before any recursion begins. Building the map is O(n) and each subsequent lookup is O(1). With this optimization, the total time complexity is O(n) because each of the n nodes is processed exactly once in O(1) work per node.

The space complexity is O(n) for the hashmap plus O(n) for the recursion call stack in the worst case (skewed tree). For a balanced tree the stack depth is O(log n), but O(n) is the correct worst-case bound.

Slicing arrays at each recursive call is expensive in both time (O(n) per slice) and space (creates new arrays). The optimal approach avoids slicing entirely by passing index boundaries instead: inorderStart and inorderEnd define the current inorder window, and a global preorderIndex pointer advances as each node is consumed.

The preorderIndex starts at 0 and increments by 1 each time a node is created — because preorder is root-left-right, consuming nodes left to right in preorder naturally gives the correct root for each subtree. This pointer is shared across all recursive calls (use a list or instance variable in Python, or a class field in Java).

The inorder boundaries are derived from the parent call: after finding the root at inorderMid, the left child gets [inorderStart, inorderMid-1] and the right child gets [inorderMid+1, inorderEnd]. The base case is when inorderStart > inorderEnd.

Python with hashmap and index pointer: def buildTree(preorder, inorder): inorderMap = {val: i for i, val in enumerate(inorder)}; preIdx = [0]; def helper(left, right): if left > right: return None; rootVal = preorder[preIdx[0]]; preIdx[0] += 1; root = TreeNode(rootVal); mid = inorderMap[rootVal]; root.left = helper(left, mid - 1); root.right = helper(mid + 1, right); return root; return helper(0, len(inorder) - 1). Time O(n), space O(n).

Java with hashmap and index pointer: class Solution { int preIdx = 0; Map<Integer,Integer> inorderMap = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i); return helper(preorder, 0, inorder.length - 1); } TreeNode helper(int[] preorder, int left, int right) { if (left > right) return null; int rootVal = preorder[preIdx++]; TreeNode root = new TreeNode(rootVal); int mid = inorderMap.get(rootVal); root.left = helper(preorder, left, mid - 1); root.right = helper(preorder, mid + 1, right); return root; } }.

Both solutions build the inorder hashmap in O(n), then recursively construct the tree in O(n) total with O(1) per node. The preorderIndex advances globally in root-left-right order, which matches preorder traversal exactly. The recursion stack depth is O(n) worst case (skewed tree) or O(log n) for balanced trees.

LeetCode 106 Construct Binary Tree from Postorder and Inorder is the direct counterpart. In postorder the root is the last element, and the same inorder-splitting logic applies. The difference is that you consume postorder from right to left and must build the right subtree before the left.

LeetCode 297 Serialize and Deserialize Binary Tree encodes a tree into a string and reconstructs it, testing your ability to use traversal order to preserve structure. LeetCode 889 Construct Binary Tree from Preorder and Postorder reconstructs a tree when both left and right subtrees have at least one node — a harder variant because without inorder the split is not uniquely determined.

The tree construction family rewards deep understanding of traversal orders. Every problem in this family reduces to identifying the root from one traversal and splitting the subarrays using another. If you internalize the preorder-gives-root, inorder-splits pattern from LeetCode 105, the variants become much more approachable.