Construct Binary Tree from Preorder and Inorder Traversal medium

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same binary tree, construct and return the binary tree.

Example 1

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Example 2

Input: preorder = [-1], inorder = [-1] Input: [-1]

Steps and Explanation

The key to solving this problem lies in understanding the properties of preorder and inorder traversals.

• Preorder traversal: The first element in the preorder array is always the root of the tree.
• Inorder traversal: The inorder traversal visits nodes in the order: left subtree, root, right subtree.

The algorithm works recursively:

1. Find the root: The first element of preorder is the root node.
2. Find the root in inorder: Locate the root node's position in the inorder array. This divides the inorder array into left and right subtrees.
3. Recursively build left and right subtrees:
   • The elements to the left of the root in inorder form the left subtree's inorder traversal. The corresponding elements in preorder (excluding the root) form the left subtree's preorder traversal.
   • The elements to the right of the root in inorder form the right subtree's inorder traversal. The corresponding elements in preorder (excluding the root and the left subtree elements) form the right subtree's preorder traversal.
4. Construct the node: Create a tree node with the root value and attach the recursively built left and right subtrees.

Code

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:
        return None

    root_val = preorder[0]
    root_index_inorder = inorder.index(root_val)

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

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

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

    return root

#Example usage
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)

#Function to print the tree (for verification - not part of the core solution)
def printTree(node):
    if node:
        print(node.val)
        printTree(node.left)
        printTree(node.right)

printTree(root)

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because each node is visited once during the traversal and construction.
• Space Complexity: O(N) in the worst case (a skewed tree) due to the recursive calls on the stack. In the average case, the space complexity is logarithmic due to the balanced nature of many binary trees.