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

The optimal solution for Construct Binary Tree from Preorder and Inorder Traversal runs in O(n) time and uses O(n) space. The time complexity is O(n) because we traverse the preorder and inorder arrays once, and the space complexity is O(n) due to the hash map storing the indices.

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

The brute force approach for Construct Binary Tree from Preorder and Inorder Traversal is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves repeatedly searching for the root of the tree in the inorder array for each node in the preorder array. This is inefficient but simple to understand. 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 Inorder Traversal?

Construct Binary Tree from Preorder and Inorder 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 Inorder Traversal?

Explain your thought process clearly. Discuss the time complexity of your approach. Be prepared to optimize your solution if asked.

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

Not using a hash map for faster index lookup in inorder. Confusing the boundaries of the preorder and inorder arrays during recursion.

#105

Construct Binary Tree from Preorder and Inorder 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 hash map to store the indices of the inorder elements for O(1) access, significantly speeding up the construction process.

⚙️

Algorithm

4 steps

1Step 1: Create a hash map to store the index of each value in the inorder array.
2Step 2: Define a recursive function that takes the current range of preorder and inorder arrays.
3Step 3: Use the first element of the preorder array as the root and find its index in the hash map.
4Step 4: Recursively construct the left and right subtrees using the ranges defined by the root index.

solution.py20 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 buildTree(self, preorder, inorder):
9        inorder_index = {value: index for index, value in enumerate(inorder)}
10        def construct(pre_start, pre_end, in_start, in_end):
11            if pre_start > pre_end or in_start > in_end:
12                return None
13            root_val = preorder[pre_start]
14            root = TreeNode(root_val)
15            root_index = inorder_index[root_val]
16            left_size = root_index - in_start
17            root.left = construct(pre_start + 1, pre_start + left_size, in_start, root_index - 1)
18            root.right = construct(pre_start + left_size + 1, pre_end, root_index + 1, in_end)
19            return root
20        return construct(0, len(preorder) - 1, 0, len(inorder) - 1)

ℹ

Complexity note: The time complexity is O(n) because we traverse the preorder and inorder arrays once, and the space complexity is O(n) due to the hash map storing the indices.

1The first element of preorder is always the root.
2Inorder helps to determine the left and right subtrees.

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