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.

• Preorder traversal: Root -> Left -> Right. The first element in the preorder array is always the root of the tree.
• Inorder traversal: Left -> Root -> Right. The inorder traversal helps us identify the left and right subtrees.

The algorithm recursively builds the tree:

1. Find the root: The first element of preorder is the root.
2. Find the root in inorder: Locate the root's position in the inorder array. This splits the inorder array into left and right subtrees.
3. Recursively build left and right subtrees:
   • The elements to the left of the root in inorder form the left subtree's inorder traversal. The corresponding elements in preorder (starting from the second element and up to the size of the left subtree) form the left subtree's preorder traversal. Recursively call the function to build the left subtree.
   • Similarly, the elements to the right of the root in inorder form the right subtree's inorder traversal. The remaining elements in preorder form the right subtree's preorder traversal. Recursively call the function to build the right subtree.
4. Connect the subtrees: Connect the left and right subtrees to the root node.

Code

#include <vector>
#include <unordered_map>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        if (preorder.empty()) return nullptr;

        //Using a hashmap for faster inorder lookup (optional optimization)
        std::unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i;
        }

        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorder_map);
    }

private:
    TreeNode* buildTreeHelper(std::vector<int>& preorder, int preStart, int preEnd, 
                              std::vector<int>& inorder, int inStart, int inEnd,
                              std::unordered_map<int, int>& inorder_map) {
        if (preStart > preEnd) return nullptr;

        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        
        //Find root in inorder using hashmap for O(1) lookup
        int rootIndex = inorder_map[rootVal];

        //Size of left subtree
        int leftSize = rootIndex - inStart;

        //Recursively build left and right subtrees
        root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1, inorder_map);
        root->right = buildTreeHelper(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd, inorder_map);

        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. The use of the unordered_map improves the lookup time to O(1) in the buildTreeHelper function. Without the hashmap, the time complexity would still be O(NlogN) due to searching in the inorder array in each recursive call.

• Space Complexity: O(N) in the worst case (skewed tree) due to the recursive call stack. The unordered_map also uses O(N) space. In the best case (balanced tree), the space complexity is O(logN).