inorder[] helps determine the left and right subtrees of the root. Elements appearing before the root in inorder[] belong to the left subtree, while elements appearing after belong to the right subtree. In our case, it is [4, 2, 5] on left and [6, 3, 7] on right. (See picture below).

See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.

construct-binary-tree-from-preorder-and-inorder-traversal-run1.excalidraw

Code

[{"language":"Java","code":"class Solution {\n    private int[] preorder;\n    private int[] inorder;\n\n\tpublic TreeNode buildTree(int[] preorder, int[] inorder) {\n\t\tif (preorder == null || preorder.length == 0 || inorder.length == 0 || preLength != inLength) {\n\t\t\treturn null;\n\t\t}\n\t\t\n\t\t// We use indices to pass subarrays, which is more efficient than copying arrays on each call.\n        this.preorder = preorder;\n        this.inorder = inorder;\n\t\n\t\tint preLength = preorder.length;\n\t\tint inLength = inorder.length;\n\t\treturn helper(preorder, inorder, 0, 0, inLength - 1);\n\t}\n\t\n\tprivate TreeNode helper(int preStart, int inStart, int inEnd) {\n\t\tif (inStart > inEnd || preStart > preorder.length - 1) {\n\t\t\treturn null;\n\t\t}\n\t\n\t\t// Pick current node from Preorder traversal using preStart and increment preStart\n\t\tTreeNode root = new TreeNode(preorder[preStart]);\n\t\n\t\t// If this node has no children then return\n\t\tif (inStart == inEnd) {\n\t\t\treturn root;\n\t\t}\n\t\n\t\t// Else find the index of this node in Inorder traversal\n\t\tint inIndex = linearSearch(inorder, root.val, inStart, inEnd);\n\t\n\t\t// Using index in Inorder traversal, construct left and right subtrees\n\t\troot.left = helper(preStart + 1, inStart, inIndex - 1);\n\t\t// We are skipping the elements on the left of the current pre order node by adding inIndex - inStart + 1\n\t\troot.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd);\n\t\n\t\treturn root;\n\t}\n\t\n\t\n\tstatic int linearSearch(int[] arr, int value, int start, int end) {\n\t\tfor (int i = start; i <= end; i++) {\n\t\t\tif (arr[i] == value) {\n\t\t\t\treturn i;\n\t\t\t}\n\t\t}\n\t\treturn -1;\n\t}\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n        if not preorder or not inorder:\n            return None\n\n        root_val = preorder[0]\n        root = TreeNode(root_val)\n\n        # This O(n) scan is the bottleneck\n        inorder_root_index = inorder.index(root_val)\n\n        # List slicing is inefficient for each recursive call\n        left_inorder = inorder[:inorder_root_index]\n        right_inorder = inorder[inorder_root_index + 1:]\n\n        left_preorder = preorder[1:1 + len(left_inorder)]\n        right_preorder = preorder[1 + len(left_inorder):]\n\n        root.left = self.buildTree(left_preorder, left_inorder)\n        root.right = self.buildTree(right_preorder, right_inorder)\n\n        return root","lang":"python"}]

Complexity

⏰ Time complexity: O(n^2) in the implementation shown above that uses linearSearch to locate the root in the inorder array. In the worst case (skewed trees), each recursive step performs an O(n) scan which leads to a quadratic total cost.
- Optimized variant: O(n) if you precompute a hash map from value → inorder index before recursion; then each node is created and positioned in O(1) work.
🧺 Space complexity: O(n) total. The output tree stores n nodes; recursion stack uses O(h) auxiliary space where h is the tree height (worst-case O(n) for a skewed tree). The optimized variant additionally requires O(n) sp

Related Tags

Continue Practicing