Construct a Binary Tree from Postorder and Inorder

Problem Statement

Given two integer arrays Postorder and Inorder. Where Postorder is the postorder traversal of a binary tree and Inorder is the inorder traversal of the same tree.

Construct and return the binary tree using the postorder and inorder arrays.

Examples

Example 1:

Input: postorder = [9, 15, 7, 20, 3] , inorder = [9, 3, 15, 20, 7]

Output : [3, 9, 20, null, null, 15, 7]

Explanation : The output tree is shown below.

Example 2:

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

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

Explanation : The output tree is shown below.

Different Approaches

1️⃣ Tree

Code:

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

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty() || postorder.empty() || inorder.size() != postorder.size()) {
            return nullptr;
        }

        // Create a map to store the indices of elements in the inorder traversal
        unordered_map<int, int> inorderMap;
        for (int i = 0; i < inorder.size(); ++i) {
            inorderMap[inorder[i]] = i;
        }

        // Call the recursive function to build the binary tree
        return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorderMap);
    }

private:
    TreeNode* buildTreeHelper(vector<int>& inorder, int inStart, int inEnd,
                              vector<int>& postorder, int postStart, int postEnd,
                              unordered_map<int, int>& inorderMap) {
        if (inStart > inEnd || postStart > postEnd) {
            return nullptr;
        }

        // Create the root node from the last element in postorder
        int rootValue = postorder[postEnd];
        TreeNode* root = new TreeNode(rootValue);

        // Find the index of rootValue in inorder to determine the left and right subtrees
        int rootIndexInorder = inorderMap[rootValue];
        int leftSubtreeSize = rootIndexInorder - inStart;

        // Recursive calls to build left and right subtrees
        root->left = buildTreeHelper(inorder, inStart, rootIndexInorder - 1,
                                     postorder, postStart, postStart + leftSubtreeSize - 1, inorderMap);
        root->right = buildTreeHelper(inorder, rootIndexInorder + 1, inEnd,
                                      postorder, postStart + leftSubtreeSize, postEnd - 1, inorderMap);

        return root;
    }
};

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

// Function to print the given vector
void printVector(vector<int>& vec) {
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    // Example input vectors
    vector<int> inorder = {40, 20, 50, 10, 60, 30};
    vector<int> postorder = {40, 50, 20, 60, 30, 10};

    // Display the input vectors
    cout << "Inorder Vector: ";
    printVector(inorder);

    cout << "Postorder Vector: ";
    printVector(postorder);

    Solution sol;

    // Build the binary tree and print its inorder traversal
    TreeNode* root = sol.buildTree(inorder, postorder);

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

    return 0;
}

Complexity Analysis:

• Time Complexity: The time complexity of the algorithm is O(N) where N is the number of nodes in the Binary Tree. This is because each node is processed and visited exactly once.
• Space Complexity: The space complexity of the algorithm is O(N + log N) where N is the number of nodes in the Binary Tree.