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] Output: [-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 the preorder array is always the root of the tree.

2. Inorder Traversal: In the inorder array, elements to the left of the root are in the left subtree, and elements to the right are in the right subtree.

The algorithm recursively constructs the tree:

1. Find the Root: The first element of preorder is the root.

2. Find the Root in Inorder: Locate the root in the inorder array. This splits the inorder array into left and right subtrees.

3. Recursively Build Subtrees: The elements to the left of the root in inorder form the left subtree's inorder traversal. The corresponding elements in preorder (from the second element up to the length of the left subtree) form the left subtree's preorder traversal. Similarly, find the inorder and preorder for the right subtree.

4. Construct the Tree: Recursively call the function to build the left and right subtrees. Connect them to the root and return the root node.

Code

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int preorderIndex = 0;

    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.Length == 0 || inorder.Length == 0) {
            return null;
        }

        Dictionary<int, int> inorderMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++) {
            inorderMap[inorder[i]] = i;
        }

        return buildTreeRecursive(preorder, inorder, inorderMap, 0, inorder.Length - 1);
    }

    private TreeNode buildTreeRecursive(int[] preorder, int[] inorder, Dictionary<int, int> inorderMap, int inorderStart, int inorderEnd) {
        if (inorderStart > inorderEnd) {
            return null;
        }

        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);

        int inorderRootIndex = inorderMap[rootVal];

        root.left = buildTreeRecursive(preorder, inorder, inorderMap, inorderStart, inorderRootIndex - 1);
        root.right = buildTreeRecursive(preorder, inorder, inorderMap, inorderRootIndex + 1, inorderEnd);

        return root;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the recursive construction.
• Space Complexity: O(N) in the worst case (a skewed tree). This is due to the recursive call stack and the inorderMap (though it could be optimized to O(log N) in some cases using a balanced tree implementation for the map).