Introduction

In this blog post, we will explore how to solve the LeetCode problem "105" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 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] Output: [-1] Constraints: 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder and inorder consist of unique values. Each value of inorder also appears in preorder. preorder is guaranteed to be the preorder traversal of the tree. inorder is guaranteed to be the inorder traversal of the tree.

Explanation

Here's the solution:

• High-level approach:

  • The first element in the preorder array is always the root of the current (sub)tree.
  • Find the index of this root in the inorder array. This index splits the inorder array into left and right subtrees.
  • Recursively build the left and right subtrees using the corresponding portions of the preorder and inorder arrays.

• Complexity:

  • Runtime: O(N), where N is the number of nodes in the tree. Storage: O(N) due to recursion stack and the hashmap

Code

    from typing import List, Optional

# 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]:
        """
        Builds a binary tree from preorder and inorder traversals.

        Args:
            preorder: The preorder traversal of the tree.
            inorder: The inorder traversal of the tree.

        Returns:
            The root of the constructed binary tree.
        """

        inorder_map = {val: i for i, val in enumerate(inorder)}  # Store inorder indices

        def build_subtree(preorder_start, preorder_end, inorder_start, inorder_end):
            """
            Recursively builds a subtree.

            Args:
                preorder_start: The starting index of the preorder array for this subtree.
                preorder_end: The ending index of the preorder array for this subtree.
                inorder_start: The starting index of the inorder array for this subtree.
                inorder_end: The ending index of the inorder array for this subtree.

            Returns:
                The root of the constructed subtree.
            """

            if preorder_start > preorder_end:
                return None

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

            root_index_inorder = inorder_map[root_val]

            left_subtree_size = root_index_inorder - inorder_start

            root.left = build_subtree(
                preorder_start + 1,
                preorder_start + left_subtree_size,
                inorder_start,
                root_index_inorder - 1,
            )

            root.right = build_subtree(
                preorder_start + left_subtree_size + 1,
                preorder_end,
                root_index_inorder + 1,
                inorder_end,
            )

            return root

        return build_subtree(0, len(preorder) - 1, 0, len(inorder) - 1)