Lecture 291:- Generating Tree from Traversals

As explained earlier, we can generate a binary tree from its inorder and preorder traversals. Here's the C++ implementation of constructing a binary tree from its inorder and preorder traversals:

cppCopy code

#include <iostream> #include <unordered_map> #include <vector> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; unordered_map<int, int> inorderMap; TreeNode* buildTreeHelper(vector<int>& preorder, int& preIndex, int inStart, int inEnd) {    if (inStart > inEnd)        return nullptr;    int rootVal = preorder[preIndex++];    TreeNode* root = new TreeNode(rootVal);    int inIndex = inorderMap[rootVal];    root->left = buildTreeHelper(preorder, preIndex, inStart, inIndex - 1);    root->right = buildTreeHelper(preorder, preIndex, inIndex + 1, inEnd);    return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {    int n = inorder.size();    for (int i = 0; i < n; ++i) {        inorderMap[inorder[i]] = i;    }    int preIndex = 0;    return buildTreeHelper(preorder, preIndex, 0, n - 1); } void printInorder(TreeNode* root) {    if (root) {        printInorder(root->left);        cout << root->val << " ";        printInorder(root->right);    } } int main() {    vector<int> preorder = {3, 9, 20, 15, 7};    vector<int> inorder = {9, 3, 15, 20, 7};    TreeNode* root = buildTree(preorder, inorder);    cout << "Inorder Traversal of Constructed Tree: ";    printInorder(root);    cout << endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left;    delete root->right;    delete root;    return 0; }

Output:

yamlCopy code

Inorder Traversal of Constructed Tree: 9 3 15 20 7

In this example, we construct a binary tree from its inorder and preorder traversals and then print the inorder traversal of the constructed tree.