105. Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solutions

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]
Output: [-1]

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # Base case: if either preorder or inorder is empty, return None
        if not preorder or not inorder:
            return None

        # The first element in preorder is the root of the tree
        root_val = preorder[0]
        root = TreeNode(root_val)

        # Find the index of the root value in the inorder array
        root_index = inorder.index(root_val)

        # Elements to the left of root_index in inorder are the left subtree
        # Elements to the right of root_index in inorder are the right subtree

        # Construct left and right subtree using recursion
        # For left subtree, pass the appropriate slices of preorder and inorder
        root.left = self.buildTree(preorder[1:root_index+1], inorder[:root_index])
        
        # For right subtree, pass the appropriate slices of preorder and inorder
        root.right = self.buildTree(preorder[root_index+1:], inorder[root_index+1:])

        # Return the constructed tree
        return root

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    // Helper function to recursively build the tree
    function helper(preorder, inorder) {
        // Base case: if either array is empty, return null
        if (preorder.length === 0 || inorder.length === 0) {
            return null;
        }
        
        // The first element in preorder is the root of the tree/subtree
        const rootVal = preorder[0];
        const root = new TreeNode(rootVal);
        
        // Find the index of the root value in the inorder array
        const rootIndex = inorder.indexOf(rootVal);
        
        // Elements to the left of rootIndex in inorder are part of the left subtree
        const leftInorder = inorder.slice(0, rootIndex);
        // Elements to the right of rootIndex in inorder are part of the right subtree
        const rightInorder = inorder.slice(rootIndex + 1);
        
        // Elements corresponding to leftInorder in preorder
        const leftPreorder = preorder.slice(1, 1 + leftInorder.length);
        // Elements corresponding to rightInorder in preorder
        const rightPreorder = preorder.slice(1 + leftInorder.length);
        
        // Recursively build the left and right subtrees
        root.left = helper(leftPreorder, leftInorder);
        root.right = helper(rightPreorder, rightInorder);
        
        // Return the constructed tree
        return root;
    }
    
    // Call the helper function with the initial arrays
    return helper(preorder, inorder);
};

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // HashMap to store the index of each value in inorder array for quick access
        Map<Integer, Integer> inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        // Call the helper function with initial parameters
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderIndexMap);
    }
    
    private TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inorderIndexMap) {
        // Base case: if there are no elements to construct the tree
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        
        // The first element of preorder is the root of the current subtree
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        
        // Get the index of the root in the inorder array
        int rootIndex = inorderIndexMap.get(rootVal);
        
        // Calculate the number of elements in the left subtree
        int leftSubtreeSize = rootIndex - inStart;
        
        // Recursively build the left subtree
        root.left = helper(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, rootIndex - 1, inorderIndexMap);
        
        // Recursively build the right subtree
        root.right = helper(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, rootIndex + 1, inEnd, inorderIndexMap);
        
        return root;
    }
}

using System.Collections.Generic;

public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        // Create a dictionary to store the index of each value in inorder array for quick access
        Dictionary<int, int> inorderIndexMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++) {
            inorderIndexMap[inorder[i]] = i;
        }
        // Call the helper function with initial parameters
        return BuildTreeHelper(preorder, 0, preorder.Length - 1, inorder, 0, inorder.Length - 1, inorderIndexMap);
    }

    private TreeNode BuildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Dictionary<int, int> inorderIndexMap) {
        // Base case: if there are no elements to construct the tree
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // The first element of preorder is the root of the current subtree
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // Get the index of the root in the inorder array
        int rootIndex = inorderIndexMap[rootVal];

        // Calculate the number of elements in the left subtree
        int leftSubtreeSize = rootIndex - inStart;

        // Recursively build the left subtree
        root.left = BuildTreeHelper(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, rootIndex - 1, inorderIndexMap);

        // Recursively build the right subtree
        root.right = BuildTreeHelper(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, rootIndex + 1, inEnd, inorderIndexMap);

        return root;
    }
}