Query: Binary Tree - Preorder, inorder and postorder iterative traversals

[NovaPrimeveera]

Dear C++ Community

I kindly want to inquire about how does replacing the stacks used with queues in preorder, inorder and postorder iterative traversal changes the traversal to a different type of traversal.

-----------------------------------------------------------------------------
For example preorder`s iterative traversal (using a stack) is:
[Reference: https://www.geeksforgeeks.org/iterative-preorder-traversal/]

   public void preorder(node* root){
          
        if (root == NULL) 
           return; 
  
    stack<node *> nodeStack; 
    nodeStack.push(root); 
  
    while (nodeStack.empty() == false) 
    { 
        
        struct node *node = nodeStack.top(); 
        printf ("%d ", node->data); 
        nodeStack.pop(); 
  
        
        if (node->right) 
            nodeStack.push(node->right); 
        if (node->left) 
            nodeStack.push(node->left); 
    } 

-----------------------------------------------------------------------------
My current deductions:
==============

When queues replace stacks in the iterative traversals the following become different traversals:

1) Preorder becomes inorder traversal

(Reason: Queue uses FIFO, it visits all its left subtree first, and prints them, but first dequeues and prints the root node and keeps a marker to then traverse the right subtree. The right subtree is then visited and printed. This results in all nodes being printed inorder)

2) Inorder becomes preorder.

3) I am unsure what Postorder becomes.

Any advice will be much appreciated

[Duthomhas]

Nothing magically changes just by using a different structure. What matters is what order you follow the rabbit holes.

Given a basic tree:

         root
        ┌───┐
     ┌──┤   ├──┐
left │  └───┘  │ right
   ┌─┴─┐     ┌─┴─┐
   │   │     │   │
   └───┘     └───┘

You can choose to visit the nodes in several different ways:

  • left, root, right : infix
  • left, right, root : prefix
  • root, left, right : postfix

The way you push it on to a stack or any other structure depends entirely on your tree traversal method.

Hope this helps.