Construct Binary Tree from Preorder and Inorder Traversal

1. Clarify the problem:

   • The problem requires us to construct a binary tree from its preorder and inorder traversals.
   • We are given two arrays: the preorder traversal and inorder traversal of the binary tree.
   • Our task is to build the binary tree and return the root node.

2. Analyze the problem:

   • Input: Two arrays representing the preorder and inorder traversals of a binary tree.
   • Output: The root node of the constructed binary tree.
   • Constraints:
     • The input arrays are guaranteed to be valid and have the same length.
     • The elements in the input arrays are unique.

3. Design an algorithm:

   • We can solve this problem using recursion.
   • The preorder traversal gives us the root element of the tree, and the inorder traversal helps us determine the left and right subtrees.
   • We start by finding the root element from the preorder traversal.
   • We locate the index of the root element in the inorder traversal, which splits the inorder traversal into the left and right subtrees.
   • Recursively construct the left and right subtrees using the respective subarrays of the inorder and preorder traversals.
   • Return the root node of the constructed binary tree.

4. Explain your approach:

   • We will define a recursive function buildTree that takes the preorder and inorder arrays as input.
   • If either array is empty, we return None, indicating the absence of a subtree.
   • We extract the root element from the preorder array, which is the first element.
   • We find the index of the root element in the inorder array.
   • We split the inorder array into the left and right subtrees based on the index.
   • We split the preorder array into the left and right subtrees accordingly.
   • We recursively call buildTree to construct the left and right subtrees.
   • We assign the returned nodes as the left and right children of the root node.
   • Finally, we return the root node.

5. Write clean and readable code:

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None

    root_val = preorder[0]
    root = TreeNode(root_val)

    root_idx = inorder.index(root_val)

    left_inorder = inorder[:root_idx]
    right_inorder = inorder[root_idx + 1:]

    left_preorder = preorder[1:1 + len(left_inorder)]
    right_preorder = preorder[1 + len(left_inorder):]

    root.left = buildTree(left_preorder, left_inorder)
    root.right = buildTree(right_preorder, right_inorder)

    return root

6. Test your code:

python

# Test case 1:
preorder1 = [3, 9, 20, 15, 7]
inorder1 = [9, 3, 15, 20, 7]
root1 = buildTree(preorder1, inorder1)
# Expected output: The constructed binary tree's structure:
#    3
#   / \
#  9  20
#    /  \
#   15   7

# Test case 2:
preorder2 = [1, 2, 3]
inorder2 = [2, 1, 3]
root2 = buildTree(preorder2, inorder2)
# Expected output: The constructed binary tree's structure:
#    1
#   / \
#  2   3

7. Optimize if necessary:

   • The provided solution has a time complexity of O(n^2) in the worst case when the binary tree is skewed.
   • We can optimize the solution by using a hashmap to store the indices of the elements in the inorder traversal, reducing the lookup time to O(1).
   • This optimization reduces the overall time complexity to O(n).

8. Handle error cases:

   • The provided solution handles the case when either the preorder or inorder array is empty by returning None, indicating the absence of a subtree.
   • We assume that the input arrays are valid and have the same length.

9. Discuss complexity analysis:

   • Time complexity: The optimized solution has a time complexity of O(n), where n is the number of nodes in the binary tree.
   • Space complexity: The space complexity is O(n) since we construct the binary tree using recursive calls, and the maximum recursion depth can be n in the worst case.