Construct Binary Tree from Inorder and Postorder Traversal Python/Java solution

In Python or Java, the standard implementation uses recursion with a HashMap (or dictionary) that maps node values to their positions in the inorder array. The algorithm processes the postorder list from the end, constructs the root, splits the inorder range, and recursively builds right and left subtrees.

What is the best approach for Construct Binary Tree from Inorder and Postorder Traversal?

The most efficient approach uses recursion with a HashMap to store inorder indices. The last element of the postorder array is always the root, and the inorder index splits the tree into left and right subtrees. Using a hash map avoids repeated searches in the inorder array, resulting in O(n) time complexity and O(n) space complexity.

Is Construct Binary Tree from Inorder and Postorder Traversal asked at Google/Amazon/Meta?

Binary tree reconstruction problems appear frequently in interviews at companies like Amazon, Google, Meta, and Microsoft. Variants include building a tree from preorder and inorder traversals or verifying traversal sequences. The problem tests understanding of tree traversal properties and divide-and-conquer recursion.

What data structure is used in Construct Binary Tree from Inorder and Postorder Traversal?

The main data structures are arrays for the traversal inputs, a hash map for fast index lookup in the inorder array, and a binary tree structure for the result. Some implementations also use a stack for an iterative solution that simulates recursion.

What is the time complexity of Construct Binary Tree from Inorder and Postorder Traversal?

The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is created exactly once, and the HashMap allows constant-time lookup of the root index in the inorder array. Space complexity is O(n) due to recursion depth and the auxiliary map.

Description Solution Video 14:31

106. Construct Binary Tree from Inorder and Postorder Traversal

Q: Is Construct Binary Tree from Inorder and Postorder Traversal easy or hard?

The problem is classified as Medium difficulty on most coding platforms. The logic becomes straightforward once you recognize that postorder's last element is the root and inorder defines subtree boundaries. Efficient solutions require understanding recursion, tree traversal patterns, and hash map optimization.

Q: How to solve Construct Binary Tree from Inorder and Postorder Traversal in O(n)?

Process the postorder array from the end because the last element represents the root. Use a HashMap to quickly locate that root in the inorder array, which divides the subtree ranges. Recursively build the right subtree first and then the left subtree while shrinking the inorder boundaries. Each element is processed once, producing O(n) time complexity.

Medium69.4% acceptance7 companies

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder and postorder consist of unique values.
Each value of postorder also appears in inorder.
inorder is guaranteed to be the inorder traversal of the tree.
postorder is guaranteed to be the postorder traversal of the tree.

Asked at 7 companies

Walmart Labs Microsoft

Google Amazon Tiktok Meta Bloomberg

Topics

14:31

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

106. Construct Binary Tree from Inorder and Postorder Traversal

Asked at 7 companies

Topics

Similar problems