# Morris Preorder Tree Traversal in C++

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:**

## Leave a Reply