Morris Preorder Tree Traversal in C++

By Pritam Hande

In this tutorial, we will learn how to implement Morris preorder tree traversal in C++. Before that let’s understand what is preorder tree traversal.

Preorder Tree Traversal: It is a type of tree traversal in which first we visit Root then Left subtree and then Right Subtree of the graph.

Steps of Morris Preorder Tree Traversal algorithm:

Step 1:

If root->left==NULL {
print root->data
root=root->right
}
else{

Find preorder predecessor

Make preorder predecessor’s right child point to the curr node.

If the right child of the preorder predecessor is already pointing to the curr node{

Set the right child to NULL.

Move to the right child of the curr node.

}
else{

Set it to the curr node.

Print the data of curr node and move to the left child of the curr node.

}
}

Step 2:

Repeat step 1 until the root becomes NULL.

Flow of Morris Preorder Tree Traversal

Input tree:

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Iteration 6:

Iteration 7:

Program to implement Morris Preorder Tree Traversal in C++

#include<iostream> 
using namespace std;

/* Each node of a tree consists of a 1 data field and 2 links, 1 for left child and 1 for right child */
typedef struct Node
{ 
  int data; 
  Node* left; 
  Node* right; 
}Node; 

Node* new_node(int );
void morris_preorder_traversal(Node*);
Node* find_preorder_predecessor(Node*);

int main() 
{ 
  Node* root = new_node(1); 
  root->left = new_node(2); 
  root->right = new_node(5); 
  root->left->left = new_node(3); 
  root->left->right = new_node(4);
  /* this input tree is shown in above figure */ 

  cout<<"Morris Preorder Traversal of the graph: ";
  morris_preorder_traversal(root);
  
  return 0; 
} 

/* This function is used to create new node with the given data */
Node* new_node(int data) 
{ 
  Node* node = new Node; 
  node->data = data; 
  node->left = NULL; 
  node->right = NULL; 
  return node; 
}

Node* find_preorder_predecessor(Node* root)
{
  Node* curr=root->left; 
  while (curr->right && curr->right != root) 
    curr=curr->right; 
  
  return curr;
}

void morris_preorder_traversal(Node* root) 
{ 
  while (root) 
  { 
    if (root->left==NULL) 
    { 
      cout<<root->data<<" "; 
      root=root->right; 
    } 
    else
    { 
      /* Finding preorder predecessor */
      Node* curr=find_preorder_predecessor(root);

      /* If preorder predecessor's right child is already pointing to root */ 
      if (curr->right == root) 
      { 
        curr->right = NULL; 
        root=root->right; 
      } 
      else
      { 
        cout<<root->data<<" "; 
        curr->right = root; 
        root = root->left; 
      } 
    } 
  } 
}

Output:

Morris Preorder Traversal of the graph: 1 2 3 4 5

Time Complexity & Space Complexity

The Time Complexity and Space Complexity of the program is O(n) and O(1) respectively.

You may also read:

1. Play Music in C++
2. Find the difference between two dates in C++