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:

1. Preorder Traversal: The first element in preorder is always the root of the tree.
2. Inorder Traversal: In inorder, elements to the left of the root are in the left subtree, and elements to the right are in the right subtree.

We can use a recursive approach:

1. Base Case: If the preorder array is empty, return null.
2. Find the Root: The first element of preorder is the root.
3. Find the Root in Inorder: Locate the root in the inorder array. This index splits the inorder array into left and right subtrees.
4. Recursive Calls: Recursively call the function to construct the left and right subtrees using the appropriate portions of preorder and inorder.
5. Construct the Node: Create a new tree node with the root value and attach the left and right subtrees.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (preorder.length === 0) {
        return null;
    }

    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    const rootIndexInInorder = inorder.indexOf(rootVal);

    // Construct left and right subtrees recursively
    root.left = buildTree(preorder.slice(1, rootIndexInInorder + 1), inorder.slice(0, rootIndexInInorder));
    root.right = buildTree(preorder.slice(rootIndexInInorder + 1), inorder.slice(rootIndexInInorder + 1));

    return root;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because we visit each node once during the recursive calls.
• Space Complexity: O(N) in the worst case (a skewed tree), due to the recursive call stack. In the average case, it's O(log N) for a balanced tree. There's also O(N) space used for the preorder and inorder array copies in the recursive calls, though this could be optimized to O(1) by passing indices instead of slicing arrays.