105. Construct Binary Tree from Preorder and Inorder Traversal

📝 Problem Details

• Title: 105. Construct Binary Tree from Preorder and Inorder Traversal
• Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
• Difficulty: Medium
• Tags/Categories: Trees In-Order-Traversal DFS Pre-Order-Traversal

💭What Were My Initial Thoughts?

- we are given to int arrays
	- preorder
	- inorder

- we need to construct the original binary tree from these two arrays
- why are we given two? why cant we reconstruct the tree with just one of them?
	- preorder: node -> left -> right
	- inorder: left -> node -> right

observations:
- preorder helps us determine the root node
- inorder helps us determine the left and right subtree boundaries
- both are needed because a single traversal alone does not provide enough information to reconstruct the tree

🤔What Did I Struggle With?

- initial comprehension / reasoning behind *why* a single traversal method is insufficient

💡 Explanation of Solution

1. understand the given traversals:
	- preorder gives the root first
	- inorder helps us find the subtree boundaries

2. identify key ideas:
	- the first element in 'preorder' is always the root
	- find this root in 'inorder' to determine the left and right subtrees
	- recursively construct the left and right subtrees

3. optimize with a hashmap:
	- instead of searching for the root in 'inorder' which is O(n) per search
	- we create a hashmap for quick lookups O(1)

4. recursive construction:
	- keep a global preIndex to track which node is being processed in 'preorder'
	- use 'inorderMap' to quickly find the root index and partition the inorder array
	- recursively construct the left and right usbtrees using the partitioned indicies

5. base case:
	- if left > right (invalid subtree) return nullptr

⌛ Complexity Analysis

Time Complexity: O(N) 
- Each node is visited once. 
- Looking up the root index in `inorderMap` takes O(1). 
- Hence, the entire process runs in O(N).

Space Complexity: O(N) 
- O(N) for the recursion stack (worst case when the tree is skewed). 
- O(N) for storing `inorderMap`. 
- Overall, O(N) additional space is required.

💻 Implementation of Solution

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inorderMap; // map to store inorder indicies
        for(int i=0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
 
        int preIndex = 0; // keep track of the root index in preorder
        return construct(preorder, inorderMap, preIndex, 0, inorder.size() -1);
    }
 
private:
    TreeNode* construct(vector<int>& preorder, unordered_map<int, int>& inorderMap, int& preIndex, int left, int right) {
        if (left > right) return nullptr;  // Base case
        
        int rootValue = preorder[preIndex++];
        TreeNode* root = new TreeNode(rootValue);
        int inorderIndex = inorderMap[rootValue];  // Get root position in inorder
        
        root->left = construct(preorder, inorderMap, preIndex, left, inorderIndex - 1);
        root->right = construct(preorder, inorderMap, preIndex, inorderIndex + 1, right);
        
        return root;
    }
};