Question: Construct Binary Tree from Preorder and Inorder Traversal

You are given two arrays - preorder and inorder, representing the preorder and inorder traversal sequences of a binary tree. Your task is to construct the binary tree from these traversal sequences and return its root.

Write a function buildTree that takes in two parameters - preorder and inorder, and returns the root node of the constructed binary tree.

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)

    mid = inorder.index(root_val)
    root.left = buildTree(preorder[1:1+mid], inorder[:mid])
    root.right = buildTree(preorder[1+mid:], inorder[mid+1:])

    return root

# Example usage
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
tree_root = buildTree(preorder, inorder)
# tree_root is the root node of the constructed binary tree

Explanation:

• The idea here is to recursively construct the binary tree using the preorder and inorder traversal sequences.
• The first element of the preorder list is the root value of the tree, so we create a TreeNode with this value.
• We then find the index of the root value in the inorder list, which divides the inorder list into left and right subtrees.
• We then recursively call buildTree for the left and right subtrees using the appropriate portions of the preorder and inorder lists.
• The base case occurs when the preorder or inorder list is empty, in which case we return None.
• Finally, we return the constructed root node of the binary tree.

The time complexity of this algorithm is O(n) where n is the number of nodes in the binary tree, as we process each node exactly once.