105. Construct Binary Tree from Preorder and Inorder Traversal - Leetcode Solution

Code Implementation

# 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, inorder):
        if not preorder or not inorder:
            return None

        # Build a hashmap to store value -> its index relations
        inorder_map = {val: idx for idx, val in enumerate(inorder)}

        def helper(pre_left, pre_right, in_left, in_right):
            if pre_left > pre_right or in_left > in_right:
                return None

            root_val = preorder[pre_left]
            root = TreeNode(root_val)
            in_root_idx = inorder_map[root_val]
            left_size = in_root_idx - in_left

            root.left = helper(pre_left + 1, pre_left + left_size, in_left, in_root_idx - 1)
            root.right = helper(pre_left + left_size + 1, pre_right, in_root_idx + 1, in_right)
            return root

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

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i;
        }
        return helper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorder_map);
    }
private:
    TreeNode* helper(const vector<int>& preorder, int pre_left, int pre_right,
                     const vector<int>& inorder, int in_left, int in_right,
                     unordered_map<int, int>& inorder_map) {
        if (pre_left > pre_right || in_left > in_right)
            return nullptr;
        int root_val = preorder[pre_left];
        TreeNode* root = new TreeNode(root_val);
        int in_root_idx = inorder_map[root_val];
        int left_size = in_root_idx - in_left;
        root->left = helper(preorder, pre_left + 1, pre_left + left_size, inorder, in_left, in_root_idx - 1, inorder_map);
        root->right = helper(preorder, pre_left + left_size + 1, pre_right, inorder, in_root_idx + 1, in_right, inorder_map);
        return root;
    }
};

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    private Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);
        int inRootIdx = inorderMap.get(rootVal);
        int leftSize = inRootIdx - inLeft;
        root.left = build(preorder, preLeft + 1, preLeft + leftSize, inLeft, inRootIdx - 1);
        root.right = build(preorder, preLeft + leftSize + 1, preRight, inRootIdx + 1, inRight);
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length || !inorder.length) return null;

    const inorderMap = {};
    for (let i = 0; i < inorder.length; i++) {
        inorderMap[inorder[i]] = i;
    }

    function helper(preLeft, preRight, inLeft, inRight) {
        if (preLeft > preRight || inLeft > inRight) return null;

        const rootVal = preorder[preLeft];
        const root = new TreeNode(rootVal);
        const inRootIdx = inorderMap[rootVal];
        const leftSize = inRootIdx - inLeft;

        root.left = helper(preLeft + 1, preLeft + leftSize, inLeft, inRootIdx - 1);
        root.right = helper(preLeft + leftSize + 1, preRight, inRootIdx + 1, inRight);
        return root;
    }

    return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

Problem Description

Given two integer arrays, preorder and inorder, representing the preorder and inorder traversal of a binary tree, construct and return the root of the binary tree. Each value in the arrays is unique, and it is guaranteed that there is exactly one valid binary tree that can be constructed from the given traversals. You must not reuse any element in the arrays.

preorder: The preorder traversal of the tree (root, left, right).
inorder: The inorder traversal of the tree (left, root, right).
Each value in preorder and inorder is unique and appears exactly once.
There is only one valid solution for the given inputs.

Thought Process

When solving this problem, the first step is to recall what preorder and inorder traversals represent:

Preorder: Always lists the root node first, then the left subtree, then the right subtree.
Inorder: Always lists the left subtree first, then the root node, then the right subtree.

The naive approach would be to repeatedly search for the root node in the inorder array for every subtree, but this would be inefficient. We need to find a way to avoid repeated searches and unnecessary work. By leveraging a hash map for quick lookups and using indices instead of slicing arrays, we can optimize the solution.

Solution Approach

To efficiently reconstruct the binary tree, follow these steps:

Build a Hash Map: Create a hash map (dictionary) to map each value in inorder to its index. This allows O(1) lookup of any value's position in the inorder traversal.
Recursive Construction: Define a recursive function that takes the current subarray boundaries for preorder and inorder (using indices, not slices).
- The first element in the current preorder range is always the root of the subtree.
- Use the hash map to find the root's index in inorder. This divides the inorder array into left and right subtrees.
- The size of the left subtree is determined by the number of elements to the left of the root in inorder.
- Recursively build the left and right subtrees by updating the boundaries for preorder and inorder accordingly.
Base Case: If the boundaries are invalid (left index > right index), return null (or None).

This approach ensures that each subtree is constructed efficiently, and each value's position is quickly found using the hash map.

Example Walkthrough

Let's walk through the process with the following example:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

First Call:
- preorder[0] is 3, so root is 3.
- Find 3 in inorder at index 1.
- Left subtree has 1 node (inorder[0]), right subtree has 3 nodes.
Left Subtree:
- Next preorder value is 9.
- 9 is at inorder[0]. No left or right children (base case).
Right Subtree:
- Next preorder value is 20.
- 20 is at inorder[3].
- Left subtree has 1 node (15), right subtree has 1 node (7).
Continue Recursion:
- For 20's left child, preorder value is 15, found at inorder[2].
- For 20's right child, preorder value is 7, found at inorder[4].
Base Case:
- All further recursive calls hit the base case (no elements), so children are null.

The constructed tree is:

Time and Space Complexity

Brute-force Approach:
- Searching for the root in inorder at every recursive call takes O(n) time, leading to O(n^2) time complexity.
Optimized Approach:
- Building the hash map takes O(n) time.
- Each node is processed exactly once, and all lookups are O(1), so the total time complexity is O(n).
- Space complexity is O(n) for the hash map and O(n) for the recursion stack (in the worst case, e.g., a skewed tree).

Summary

This problem leverages the unique properties of preorder and inorder traversals to reconstruct a binary tree. By using a hash map for quick index lookups and recursive construction with index boundaries, we achieve an efficient O(n) solution. The elegance comes from the direct mapping between traversal orders and tree structure, combined with careful management of subarray indices to avoid unnecessary copying or searching.

AlgoMap.io

Want Help Cracking FAANG?