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 using in-order and preorder arrays.

Examples

Example 1:

Input: preorder = [3, 9, 20, 15, 7] , inorder = [9, 3, 15, 20, 7]
Output : [3, 9, 20, null, null, 15, 7]

Explanation : The output tree is shown below.

Example 2:

Input : preorder = [3, 4, 5, 6, 2, 9] , inorder = [5, 4, 6, 3, 2, 9]

Output : [3, 4, 2, 5, 6, null, 9]

Explanation : The output tree is shown below.

Different Approach

1️⃣ Tree

Code:

#include <bits/stdc++.h>
using namespace std;

// TreeNode structure
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to build a binary tree
    // from preorder and inorder traversals
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // Create a map to store indices
        // of elements in the inorder traversal
        unordered_map<int, int> inMap;

        // Populate the map with indices
        // of elements in the inorder traversal
        for (int i = 0; i < inorder.size(); i++) {
            inMap[inorder[i]] = i;
        }

        // Call the private helper function
        // to recursively build the tree
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inMap);
    }

private:
    // Recursive helper function to build the tree
    TreeNode* buildTree(vector<int>& preorder, int preStart, int preEnd,
                        vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& inMap) {
        // Base case: If the start indices
        // exceed the end indices, return null
        if (preStart > preEnd || inStart > inEnd) {
            return nullptr;
        }

        // Create a new TreeNode with value
        // at the current preorder index
        TreeNode* root = new TreeNode(preorder[preStart]);

        // Find the index of the current root
        // value in the inorder traversal
        int inRoot = inMap[root->data];

        // Calculate the number of
        // elements in the left subtree
        int numsLeft = inRoot - inStart;

        // Recursively build the left subtree
        root->left = buildTree(preorder, preStart + 1, preStart + numsLeft,
                               inorder, inStart, inRoot - 1, inMap);

        // Recursively build the right subtree
        root->right = buildTree(preorder, preStart + numsLeft + 1, preEnd,
                                inorder, inRoot + 1, inEnd, inMap);

        // Return the current root node
        return root;
    }

    // Function to print the
    // inorder traversal of a tree
    void printInorder(TreeNode* root) {
        if (root != nullptr) {
            printInorder(root->left);
            cout << root->data << " ";
            printInorder(root->right);
        }
    }

    // Function to print the
    // given vector
    void printVector(vector<int>& vec) {
        for (int i = 0; i < vec.size(); i++) {
            cout << vec[i] << " ";
        }
        cout << endl;
    }

public:
    void run() {
        vector<int> inorder = {9, 3, 15, 20, 7};
        vector<int> preorder = {3, 9, 20, 15, 7};

        cout << "Inorder Vector: ";
        printVector(inorder);

        cout << "Preorder Vector: ";
        printVector(preorder);

        TreeNode* root = buildTree(preorder, inorder);

        cout << "Inorder of Unique Binary Tree Created:" << endl;
        printInorder(root);
        cout << endl;
    }
};

int main() {
    Solution sol;
    sol.run();
    return 0;
}

Complexity Analysis:

• Time Complexity: The time complexity is O(N), where N is the number of nodes in the Binary Tree. This is because each node of the Binary Tree is visited once.
• Space Complexity:O(N), where N is the number of nodes in the Binary Tree. The inorder hashmap used to store the inorder array for fast lookup takes up space proportional to the input nodes. Additionally, an auxiliary stack space of approximately O(H) is used, where H is the height of the Binary Tree