C++: implement a non-recursive version or inorder traversal for binary tree. Ple

Question

C++:

implement a non-recursive version or inorder traversal for binary tree. Please implement the nonRecInorder() function as well as the levelOrder() function:

Important:

-The algorithm of this non-recursive inorder traversal is listed as follows.

Create an TreeNode* stack while(true)

while(root is not nullptr){ push(root)
root = root->left;

}
if(stack is empty) break;

root = top(); pop();

print out the datum of root

root = root->right; }

-The algorithm of level order traversal is listed as follows.

Create a queue
If(root is not nullptr) push root to the queue

While(queue is not empty){

temp = Dequeu()

Print out datum of temp

If left pointer of temp is not nullptr, push it to the queue

If right pointer of temp is not nullptr, push it to the queue }

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

// Tree Node has data, left pointer, right pointer
struct TreeNode
{
    int datum;
    struct TreeNode* left;
    struct TreeNode* right;
};

// create a new node with given value, left and right pointers are nullptr
struct TreeNode* newTreeNode(int value)
{
    struct TreeNode* node = new struct TreeNode;
    node->datum = value;
    node->left = nullptr;
    node->right = nullptr;
    return(node);
}

// Non-recursive traverse a binary tree
// print out the values by inorder
// it uses stack to store the nodes
void noRecInorder(TreeNode *root)
{
  
}

// level order traversal
// It uses queue to store the values of the next level
void levelOrder(TreeNode *root){

}

// Driver program to test above functions
int main()
{
    /* Constructed binary tree is
        100
      /    
      9      10
     /     /
     9   4 7
     */
    struct TreeNode *root = newTreeNode(100);
    root->left        = newTreeNode(9);
    root->right       = newTreeNode(10);
    root->left->left = newTreeNode(9);
    root->left->right = newTreeNode(4);
    root->right->left = newTreeNode(7);
  
    cout << "Inorder traversal result:" << endl;;
    noRecInorder(root);
    cout << "Level traversal result:" << endl;
  
    levelOrder(root);
  
    return 0;
}

Explanation / Answer

void noRecInorder(struct TreeNode *root)

{

  struct TreeNode *cur = root;

  struct TreeNode *stack = nullptr;

  char flag = 0;

  while (!flag)

  {

    /* Reach the left most */

    if(cur != nullptr)

    {

      push(&stack, cur);                                              

      cur = cur->left;

    }

    else                                                             

    {

      if (stack != nullptr)

      {

        cur = pop(&stack);

        printf("%d ", cur-> datum);

        cur = cur->right;

      }

      else

        flag = 1;

    }

  } /* END OF WHILE LOOP */

}    

Above code is for inorder traversal without using recursion. I hope you will be able to write the helper function code like (push and pop of stack).

void levelOrder(struct TreeNode* root)

{

    int rear,

int front;

    struct TreeNode **queue = CREATE_QUEUE(&front, &rear);

    struct TreeNode *temp= root;

    while (temp)

    {

        printf("%d ", temp->datum);

        /*Enqueue the left child */

        if (temp->left)

            ENQUEUE(queue, &rear, temp->left);

        /*Enqueue the right child */

        if (temp->right)

            ENQUEUE(queue, &rear, temp->right);

        /* make dequeue node to temp */

        temp = DEQUEUE(queue, &front);

    }

}

This is similar like breadth first search algo.

I hope you will be able to write the helper enqueue/dequeue/createqueue code.

Feel free to ask any query.

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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