Construct Binary Tree
Given two integer arrays, preorder and inorder, which represent the pre-order and in-order traversal of a binary tree, construct and return the binary tree.
- Pre-order traversal visits nodes in this order: root → left subtree → right subtree
- In-order traversal visits nodes in this order: left subtree → root → right subtree
You need to construct the binary tree and return its root node.
Examples
preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7] output: [3, 9, 20, null, null, 15, 7] Explanation: Given the two arrays, the binary tree constructed is: 3 / \ 9 20 / \ 15 7
preorder = [1, 2], inorder = [2, 1] output: [1, 2] Explanation: Given the two arrays, the binary tree constructed is: 1 / 2
Constraints:
- The number of nodes in the tree is in the range
[1, 3000]. preorderandinorderconsist of unique integers.- The elements of
inorderwill always be the same as the elements ofpreorderbut in a different order.
Our solution to construct a binary tree from pre-order and in-order traversal arrays uses a recursive approach. We first identify the root node from the pre-order array, then split the in-order array into left and right subtrees based on the root's position in the in-order array. We continue this process recursively to build the entire binary tree.
- We start by picking the first element of the
preorderarray as the root of the tree. The index of this root element in theinorderarray helps us divide the tree into left and right subtrees. - The elements to the left of the root in the
inorderarray form the left subtree, and the elements to the right form the right subtree. - We then recursively build the left and right subtrees using the next available elements in the
preorderarray.
To ensure efficient lookups of the root's index in the inorder array, we create a hash map (inorder_index_map) that maps values to their indices in the inorder array. This allows us to retrieve the position of the root in constant time.
Recursion:
- Base Case: If there are no elements to construct the tree (i.e., the
preorderorinorderarray is empty), we returnnullptr. - Recursive Step: We extract the root from the
preorderarray and find its position in theinorderarray using the hash map. This splits theinorderarray into left and right subtrees. We then recursively build the left and right subtrees and attach them to the root.
By maintaining the correct indices for both the pre-order and in-order arrays, we can recursively construct the entire tree.
from typing import List, Optional
class TreeNode:
def __init__(self, value: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
self.value = value
self.left = left
self.right = right
def build_tree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
inorder_index = inorder.index(root_val)
# Construct left and right subtree
root.left = build_tree(preorder[1:1 + inorder_index], inorder[:inorder_index])
root.right = build_tree(preorder[1 + inorder_index:], inorder[inorder_index + 1:])
return rootTime Complexity: The solution has a time complexity of O(n), where n is the number of elements in the tree. This is because we traverse both the preorder and inorder arrays once, and we use a hash map for constant-time lookups of root indices in the inorder array.
Space Complexity: The solution uses O(n) space for the hash map that stores the indices of elements in the inorder array, and the recursion stack requires O(h) space, where h is the height of the tree. In the worst case (a skewed tree), the height of the tree can be O(n), so the total space complexity is O(n).
