Morris Inorder Traversal

Inorder traversal with no recursion

Introduction

Morris Inorder Traversal efficiently visits nodes in inorder sequence by eliminating the need for recursion or a stack, offering O(1) space complexity with threaded binary trees.

How Morris Inorder works?

1

Start with the Root Node

  • Begin at the root node of the tree.
2

Find the Inorder Predecessor

  • For each node, find its inorder predecessor.
3

Create Temporary Link

  • Establish a temporary link from the predecessor’s right child to the current node.
4

Move to Left Child

5

Visit the Current Node

  • When there’s no left child, visit the current node.
6

Break the Link

  • Once done with the left subtree, break the temporary link and move to the right child.
7

Repeat

  • Continue this process until all nodes are visited.

Implementation of Level Order Traversal (BFS)

//morrisinorder.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
    this->data = data;
    this->left = NULL;
    this->right = NULL;
}
};
Node *buildTree(Node *root)
{
cout << "Enter The data: " << endl;
int data;
cin >> data;
root = new Node(data);
if (data == -1)
{
    return NULL;
}
cout << "Enter data for left : " << endl;
root->left = buildTree(root->left);
cout << "Enter data for right: " << endl;
root->right = buildTree(root->right);
return root;
}
void morrisinorder(Node* root) {
    Node* cur=root;
    while(cur!=NULL){
        if(cur->left==NULL){
            cout<<cur->data<<" ";
            cur=cur->right;
        }
        else{
            Node* leftChild = cur->left;
            while(leftChild->right != NULL){
                leftChild= leftChild->right;
            }
            leftChild->right=cur;
            Node* temp=cur;
            cur=cur->left;
           temp->left=NULL;
        }
    }
}
int main()
{
// creating tree
Node *root = NULL;
root = buildTree(root);

// morris inorder
morrisinorder(root);
}

Time Complexity

  • Time Complexity:O(n)
  • Each node in the tree is visited once, and we do not revisit nodes. The traversal only involves constant-time operations (checking and modifying pointers), resulting in linear time proportional to the number of nodes, n.

Space Complexity

  • Space Complexity:O(1)