C++: Construct Binary Tree from Preorder and Inorder Traversal

Thought Process

The first element in the preorder array is always the root of the tree. We find the index of this root in the inorder array to determine the left and right subtrees. To build the left subtree, we recursively use the elements before the root in the inorder array. For the right subtree, we use the elements after the root. This ensures that the tree is constructed correctly. 

/**
 * Definition for a binary tree node.
 * 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:
    int idx=0;
    int search(vector<int>& inorder,int target){

        for(int i=0;i<inorder.size();i++){
            if(inorder[i]==target){
                return i;
            }
        }
        return -1;
    }
    TreeNode* makeTree(vector<int>& preorder, vector<int>& inorder, int start, int end){

        if(start>end)
            return NULL;

        int root = preorder[idx];
        int indexOfRoot = search(inorder,root);
        idx++;

        TreeNode* rootNode = new TreeNode(root);

        if(start==end)
            return rootNode;

        rootNode->left = makeTree(preorder,inorder,start,indexOfRoot-1);
        rootNode->right = makeTree(preorder,inorder,indexOfRoot+1,end);

        return rootNode;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        int start = 0;
        int end = preorder.size()-1;

        TreeNode* nod = makeTree(preorder,inorder,start,end);
        return nod;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(n)

The space used by the recursion stack depends on the height of the tree. In the worst case, the space complexity is O(n).

Code copied!