preorder traversal without recursion

void iterativePreorder(node *root) { // Base Case if (root == NULL) return; // Create an empty stack and push root to it stack<node *> nodeStack; nodeStack.push(root); while (nodeStack.empty() == false) { // Pop the top item from stack and print it struct node *node = nodeStack.top(); printf ("%d ", node->data); nodeStack.pop(); // Push right and left children of the popped node to stack if (node->right) nodeStack.push(node->right); if (node->left) nodeStack.push(node->left); } }

//Iterative Inorder binary tree traversal void it_inOrder(btree *root) { stack<btree*> s; while(root || !s.empty()) { while(root) { s.push(root); root=root->left; } btree *p=s.top(); s.pop(); cout<<p->data<<" "; root=p->right; } }

inorder traversal without recursion and stack

//Pragram in C++ to do inorder traversal of binary tree without recursion and stack
//using morris inorder traversal
btree* find_predecessesor(btree *root){
    btree *head = root;
    root = root->left;
  
    //go to rightmost node of left subtree
    while(root->right && root->right != head){
        root = root->right;
    }
    
    return root;
}

void morris_inorder(btree *root){
    while(root){
        if(!root->left){
          //when left subtree is empty
            cout<<root->data<<" ";
            root = root->right;
        } else{
            btree *link = find_predecessesor(root);
            if(link->right){
              //if left subtree has already been traversed
                link->right = NULL;
                cout<<root->data<<" ";
                root=root->right;
            } 
            else{
              //link predecessor node to current node 
                link->right = root;
                root=root->left;
            } 
        }
    }
}

Posted by: Guest on October-07-2021

1.1 Create an empty stack 2.1 Do following while root is not NULL a) Push root's right child and then root to stack. b) Set root as root's left child. 2.2 Pop an item from stack and set it as root. a) If the popped item has a right child and the right child is at top of stack, then remove the right child from stack, push the root back and set root as root's right child. b) Else print root's data and set root as NULL. 2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

Code answers related to "preorder traversal without recursion"

Code answers related to "Whatever"

Browse Popular Code Answers by Language

Answers for "preorder traversal without recursion"

Code answers related to "preorder traversal without recursion"

Code answers related to "Whatever"

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us