Question

C++ code (just fuction)

Binary Search Tree (BTS)

1) Algorithm for all traversals (inorder, preorder, postorder, level order), done nonrecursively

2)Ability to provide the result of traversing a tree in all traversals (inorder, preorder, postorder, level order)

Answer 1

Answer:-
(1) Inorder Traversal:
Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Preorder Traversal:
Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)

Postorder Traversal:
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.

(2)
In order using C++ without recursion:-

#include <stdio.h>
#include <stdlib.h>
/* A binary tree tNode has data, a pointer to left child and a pointer to right child */
struct tNode {
    int data;
    struct tNode* left;
    struct tNode* right;
};
/* Function to traverse the binary tree without recursion and without stack */
void MorrisTraversal(struct tNode* root)
{
    struct tNode *current, *pre;
    if (root == NULL)
        return;
    current = root;
    while (current != NULL) {
        if (current->left == NULL) {
            printf("%d ", current->data);
            current = current->right;
        }
        else {
            /* Find the inorder predecessor of current */
            pre = current->left;
            while (pre->right != NULL && pre->right != current)
                pre = pre->right
            /* Make current as the right child of its inorder
               predecessor */
            if (pre->right == NULL) {
                pre->right = current;
                current = current->left;
            }
            /* Revert the changes made in the 'if' part to restore
               the original tree i.e., fix the right child
               of predecessor */
            else {
                pre->right = NULL;
                printf("%d ", current->data);
                current = current->right;
            } /* End of if condition pre->right == NULL */
        } /* End of if condition current->left == NULL*/
    } /* End of while */
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new tNode with the given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
    struct tNode* node = new tNode;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
*/Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
            1
          /   \
        2     3
       /   \
      4     5
*/
    struct tNode* root = newtNode(1);
    root->left = newtNode(2);
    root->right = newtNode(3);
    root->left->left = newtNode(4);
    root->left->right = newtNode(5);
    MorrisTraversal(root);
return 0;
}
Output:-4 2 5 1 3

Post order using C++ without recursion:-
#include <bits/stdc++.h>
using namespace std;  
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
    int data;
    struct Node *left, *right;
    bool visited;
};
void postorder(Node* root)
{
    Node* n = root;
    unordered_map<Node*, Node*> parentMap;
    parentMap.insert(pair<Node*, Node*>(root, nullptr))
    while (n) {
        if (n->left && parentMap.find(n->left) == parentMap.end()) {
            parentMap.insert(pair<Node*, Node*>(n->left, n));
            n = n->left;
        }
        else if (n->right && parentMap.find(n->right) == parentMap.end()) {
            parentMap.insert(pair<Node*, Node*>(n->right, n));
            n = n->right;
        }
        else {
            cout << n->data << " ";
            n = (parentMap.find(n))->second;
        }
    }
}
struct Node* newNode(int data)
{
    struct Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->visited = false;
    return (node);
}
/* Driver program to test above functions*/
int main()
{
    struct Node* root = newNode(8);
    root->left = newNode(3);
    root->right = newNode(10);
    root->left->left = newNode(1);
    root->left->right = newNode(6);
    root->left->right->left = newNode(4);
    root->left->right->right = newNode(7);
    root->right->right = newNode(14);
    root->right->right->left = newNode(13);
    postorder(root);
    return 0;
}
Output:- 1 4 7 6 3 13 14 10 8

Pre order using C++ without recursion:
#include <bits/stdc++.h>
using namespace std;
// Structure of a node of an n-ary tree
struct Node {
    char key;
    vector<Node*> child;
};  
// Utility function to create a new tree node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    return temp;
}
// Function to traverse tree without recursion
void traverse_tree(struct Node* root)
{
    // Stack to store the nodes stack<Node*> nodes;
    // push the current node onto the stack
    nodes.push(root);
    // loop while the stack is not empty
    while (!nodes.empty()) {
        // store the current node and pop it from the stack
        Node* curr = nodes.top();
        nodes.pop();
        // current node has been travarsed
     if(curr != NULL)
      {
         cout << curr->key << " ";
        // store all the childrent of current node from
        // right to left.
        vector<Node*>::iterator it = curr->child.end();
        while (it != curr->child.begin()) {
            it--;
            nodes.push(*it);
        }
      }
    }
}
// Driver program
int main()
{
    /*   Let us create below tree
   *            A
   *        / / \ \
   *       B F   D E
   *      / \     | /|\
   *     K J     G C H I
   *    / \         |   |
   *   N   M        O   L
   */
    Node* root = newNode('A');
    (root->child).push_back(newNode('B'));
    (root->child).push_back(newNode('F'));
    (root->child).push_back(newNode('D'));
    (root->child).push_back(newNode('E')); (root>child[0]>child).push_back(newNode('K')); (root>child[0]>child).push_back(newNode('J')); (root>child[2]>child).push_back(newNode('G')); (root>child[3]>child).push_back(newNode('C')); (root>child[3]>child).push_back(newNode('H'));    (root>child[3]>child).push_back(newNode('I')); (root>child[0]>child[0]>child).push_back(newNode('N')); (root>child[0]>child[0]>child).push_back(newNode('M')); (root>child[3]>child[0]>child).push_back(newNode('O')); (root>child[3]>child[2]>child).push_back(newNode('L'));
    traverse_tree(root);
    return 0;
}