Lecture 290:- Can we Generate Tree from Traversals

Yes, it is possible to generate a binary tree from its traversals (preorder, inorder, and postorder). Each of these traversals provides some specific information about the binary tree, which can be used to construct the tree. Here are the steps to generate a binary tree from its traversals:

1. Preorder Traversal:
   • The first element of the preorder traversal is always the root of the tree.
   • Find the root in the inorder traversal. Elements to the left of the root in the inorder traversal represent the left subtree, and elements to the right represent the right subtree.
   • Recursively construct the left and right subtrees using the elements found in the inorder traversal.
2. Inorder Traversal:
   • The root of the binary tree is the middle element of the inorder traversal.
   • Elements to the left of the root represent the left subtree, and elements to the right represent the right subtree.
   • Recursively construct the left and right subtrees using the elements found in the inorder traversal.
3. Postorder Traversal:
   • The last element of the postorder traversal is always the root of the tree.
   • Find the root in the inorder traversal. Elements to the left of the root in the inorder traversal represent the left subtree, and elements to the right represent the right subtree.
   • Recursively construct the left and right subtrees using the elements found in the inorder traversal.

It's important to note that for uniquely constructing the binary tree, all three traversals (preorder, inorder, and postorder) must be given or some additional information is required.

Here's an example of how to construct a binary tree from its inorder and preorder traversals:

cppCopy code

#include <iostream> #include <unordered_map> 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.