Morris Preorder Traversal

Preorder traversal with no recursion

Introduction

Morris Preorder Traversal is an efficient method to visit nodes in preorder sequence without using recursion or a stack, achieving O(1) space by leveraging threaded binary trees.

How Morris Preorder works?

1

Start with the Root Node

  • Begin at the root node of the tree.
2

Find the Inorder Predecessor

  • Find the inorder predecessor (rightmost node in the left subtree).
3

Create Temporary Link

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

Visit the Current Node

5

Move to Left Child

  • Move to the left child if it exists otherwise, go to the right child.
6

Break the Link

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

Repeat

  • Continue until all nodes are visited.

Implementation of Level Order Traversal (BFS)

//morrispreorder.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 morrispreorder(Node* root) {
    Node* curr=root;
    while(curr){
        if(curr->left==NULL){
            cout<<curr->data<<" ";
            curr=curr->right;
        }
        else{
            cout<<curr->data<<" ";
            Node* leftChild=curr->left;
            while(leftChild->right!=NULL){
                leftChild=leftChild->right;
            }
            leftChild->right=curr->right;
            Node *temp=curr;
            curr=curr->left;
            temp->left=NULL;
        }
    }
}
int main()
{
// creating tree
Node *root = NULL;
root = buildTree(root);

// morris preorder
morrispreorder(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)