What is the brute force solution for Construct Binary Tree from Preorder and Postorder Traversal?

The brute force approach for Construct Binary Tree from Preorder and Postorder Traversal is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves recursively finding the root from the preorder array and then determining the left and right subtrees by searching in the postorder array. This method is straightforward but inefficient due to repeated searches. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Construct Binary Tree from Preorder and Postorder Traversal?

Construct Binary Tree from Preorder and Postorder Traversal uses the following concepts: Array, Hash Table, Divide and Conquer, Tree, Binary Tree. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Construct Binary Tree from Preorder and Postorder Traversal?

Explain your thought process clearly while coding. Consider edge cases and base cases upfront. Practice similar problems to recognize patterns in tree construction.

What are common mistakes when solving Construct Binary Tree from Preorder and Postorder Traversal?

Not handling base cases correctly in recursion. Forgetting to update the bounds correctly when constructing subtrees.

#889

Construct Binary Tree from Preorder and Postorder Traversal

Medium

ArrayHash TableDivide and ConquerTreeBinary TreeHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a hashmap to store the indices of the postorder elements, allowing for O(1) access during subtree size calculations. This reduces the overall time complexity significantly.

⚙️

Algorithm

6 steps

1Step 1: Create a hashmap to store the indices of each value in the postorder array for quick access.
2Step 2: Define a recursive function that takes the current bounds of the preorder and postorder arrays.
3Step 3: Base case: if the bounds are invalid, return None.
4Step 4: Create the root node from the current preorder element and find the size of the left subtree using the hashmap.
5Step 5: Recursively construct the left and right subtrees using the updated bounds.
6Step 6: Return the constructed tree node.

solution.py21 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def constructFromPrePost(self, preorder, postorder):
9        index_map = {value: i for i, value in enumerate(postorder)}
10        def build(pre_start, pre_end, post_start, post_end):
11            if pre_start > pre_end:
12                return None
13            root = TreeNode(preorder[pre_start])
14            if pre_start == pre_end:
15                return root
16            left_root = preorder[pre_start + 1]
17            left_size = index_map[left_root] - post_start + 1
18            root.left = build(pre_start + 1, pre_start + left_size, post_start, post_start + left_size - 1)
19            root.right = build(pre_start + left_size + 1, pre_end, post_start + left_size, post_end - 1)
20            return root
21        return build(0, len(preorder) - 1, 0, len(postorder) - 1)

ℹ

Complexity note: The time complexity is O(n) because we only traverse the preorder and postorder arrays a constant number of times, and the space complexity is O(n) due to the hashmap storing indices.

1Understanding the relationship between preorder and postorder traversals is crucial.
2Using a hashmap for index lookups can significantly optimize the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.