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

Python, Java, C++, C#, and JavaScript implementations typically follow the same recursive structure. The function tracks preorder and postorder index ranges, constructs the root, finds the left subtree size using a hash map, and recursively builds the children. Each language version runs in O(n) time with O(n) extra space.

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

The most efficient approach uses recursion with a hash map that stores the index of each value in the postorder traversal. Preorder gives the root immediately, and the next preorder value identifies the left subtree root. A hash lookup determines the subtree size in O(1), allowing the tree to be built recursively in O(n) time.

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

Binary tree reconstruction problems frequently appear in interviews at companies like Amazon, Google, Meta, and Microsoft. Variants include building trees from inorder + preorder or inorder + postorder. This version tests understanding of traversal properties and recursive divide and conquer.

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

The core data structure is a binary tree built through recursive calls. An auxiliary hash map is commonly used to store postorder indices for constant‑time lookup. The algorithm also relies on array indexing and divide‑and‑conquer recursion.

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

The optimized solution runs in O(n) time because each node is processed once and subtree boundaries are found using constant‑time hash lookups. A simpler version that scans the postorder array for each subtree takes O(n²) in the worst case. Space complexity is O(n) for the hash map plus recursion stack.

Description Solution Video 22:56

889. Construct Binary Tree from Preorder and Postorder Traversal

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

The problem is rated Medium because identifying the root is simple but determining subtree boundaries requires understanding how preorder and postorder interact. Once you recognize that the second preorder element marks the left subtree root, the divide‑and‑conquer recursion becomes straightforward.

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

Create a hash map from node value to its index in the postorder traversal. During recursion, use preorder to identify the root and the left subtree root. The hash map gives the left subtree boundary instantly, allowing you to split the traversal ranges and build the tree recursively in linear time.

Medium78.0% acceptance6 companies

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

Constraints:

1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
All the values of preorder are unique.
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
All the values of postorder are unique.
It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Asked at 6 companies

Apple

Google Amazon Microsoft Meta Bloomberg

Topics

22:56

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

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,4,5,3,6,7]
[4,5,2,6,7,3,1]

Input

[1]
[1]

Your code is saved on this device.Solution