Done using recursion in c++ In this problem you are going to reconstruct a tree

Question

Done using recursion in c++

In this problem you are going to reconstruct a tree using its postorder and inorder traversals, and print the level order traversal for the reconstructed tree. On the first line, you can read the number of elements in the tree. In the second line you can read the postorder traversal of the tree, in a format similar to the output format for problem 1, i.e. the data for each node is printed followed by a space. On the third line you can read the inorder traversal in a similar format. The output should be one line containing the levelorder in a similar format to the problem 2.

Explanation / Answer

/* C++ program to print level order traversal using STL */

#include <iostream>

#include <queue>

using namespace std;

// A Binary Tree Node

struct Node

{

    int data;

    struct Node *left, *right;

};

// Iterative method to find height of Bianry Tree

void printLevelOrder(Node *root)

{

    // Base Case

    if (root == NULL) return;

    // Create an empty queue for level order tarversal

    queue<Node *> q;

    // Enqueue Root and initialize height

    q.push(root);

    while (q.empty() == false)

    {

        // Print front of queue and remove it from queue

        Node *node = q.front();

        cout << node->data << " ";

        q.pop();

        /* Enqueue left child */

        if (node->left != NULL)

            q.push(node->left);

        /*Enqueue right child */

        if (node->right != NULL)

            q.push(node->right);

    }

}

// Utility function to create a new tree node

Node* newNode(int data)

{

    Node *temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

// Driver program to test above functions

int main()

{

    // Let us create binary tree shown in above diagram

    Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    cout << "Level Order traversal of binary tree is ";

    printLevelOrder(root);

    return 0;

}

post order: g h d e b i f c a

inorder : g d h b e a c i f

Preorder : g h d e b i f c a

Level order : a b c d e f g h i

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.