Morris traversal for Preorder

Last Updated : 11 Sep, 2023

Using Morris Traversal, we can traverse the tree without using stack and recursion. The algorithm for Preorder is almost similar to Morris traversal for Inorder.

1...If left child is null, print the current node data. Move to right child.
….Else, Make the right child of the inorder predecessor point to the current node. Two cases arise:
………a) The right child of the inorder predecessor already points to the current node. Set right child to NULL. Move to right child of current node.
………b) The right child is NULL. Set it to the current node. Print the current node’s data and move to left child of current node.
2...Iterate until the current node is not NULL.

Following is the implementation of the above algorithm.

C++

// C++ program for Morris Preorder traversal  
#include <bits/stdc++.h> 
using namespace std;  
  
class node  
{  
    public: 
    int data;  
    node *left, *right;  
};  
  
/* Helper function that allocates a new node with the  
given data and NULL left and right pointers. */
node* newNode(int data)  
{  
    node* temp = new node(); 
    temp->data = data;  
    temp->left = temp->right = NULL;  
    return temp;  
}  
  
// Preorder traversal without recursion and without stack  
void morrisTraversalPreorder(node* root)  
{  
    while (root)  
    {  
        // If left child is null, print the current node data. Move to  
        // right child.  
        if (root->left == NULL)  
        {  
            cout<<root->data<<" ";  
            root = root->right;  
        }  
        else
        {  
            // Find inorder predecessor  
            node* current = root->left;  
            while (current->right && current->right != root)  
                current = current->right;  
  
            // If the right child of inorder predecessor already points to  
            // this node  
            if (current->right == root)  
            {  
                current->right = NULL;  
                root = root->right;  
            }  
  
            // If right child doesn't point to this node, then print this  
            // node and make right child point to this node  
            else
            {  
                cout<<root->data<<" ";  
                current->right = root;  
                root = root->left;  
            }  
        }  
    }  
}  
  
// Function for Standard preorder traversal  
void preorder(node* root)  
{  
    if (root)  
    {  
        cout<<root->data<<" ";  
        preorder(root->left);  
        preorder(root->right);  
    }  
}  
  
/* Driver program to test above functions*/
int main()  
{  
    node* root = NULL;  
  
    root = newNode(1);  
    root->left = newNode(2);  
    root->right = newNode(3);  
  
    root->left->left = newNode(4);  
    root->left->right = newNode(5);  
  
    root->right->left = newNode(6);  
    root->right->right = newNode(7);  
  
    root->left->left->left = newNode(8);  
    root->left->left->right = newNode(9);  
  
    root->left->right->left = newNode(10);  
    root->left->right->right = newNode(11);  
  
    morrisTraversalPreorder(root);  
  
    cout<<endl;  
    preorder(root);  
  
    return 0;  
}  
  
//This code is contributed by rathbhupendra 

C

// C program for Morris Preorder traversal 
#include <stdio.h> 
#include <stdlib.h> 
  
struct node 
{ 
    int data; 
    struct node *left, *right; 
}; 
  
/* Helper function that allocates a new node with the 
   given data and NULL left and right pointers. */
struct node* newNode(int data) 
{ 
    struct node* temp = (struct node*) malloc(sizeof(struct node)); 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
// Preorder traversal without recursion and without stack 
void morrisTraversalPreorder(struct node* root) 
{ 
    while (root) 
    { 
        // If left child is null, print the current node data. Move to 
        // right child. 
        if (root->left == NULL) 
        { 
            printf( "%d ", root->data ); 
            root = root->right; 
        } 
        else
        { 
            // Find inorder predecessor 
            struct node* current = root->left; 
            while (current->right && current->right != root) 
                current = current->right; 
  
            // If the right child of inorder predecessor already points to 
            // this node 
            if (current->right == root) 
            { 
                current->right = NULL; 
                root = root->right; 
            } 
  
            // If right child doesn't point to this node, then print this 
            // node and make right child point to this node 
            else
            { 
                printf("%d ", root->data); 
                current->right = root; 
                root = root->left; 
            } 
        } 
    } 
} 
  
// Function for Standard preorder traversal 
void preorder(struct node* root) 
{ 
    if (root) 
    { 
        printf( "%d ", root->data); 
        preorder(root->left); 
        preorder(root->right); 
    } 
} 
  
/* Driver program to test above functions*/
int main() 
{ 
    struct node* root = NULL; 
  
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
  
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
  
    root->right->left = newNode(6); 
    root->right->right = newNode(7); 
  
    root->left->left->left = newNode(8); 
    root->left->left->right = newNode(9); 
  
    root->left->right->left = newNode(10); 
    root->left->right->right = newNode(11); 
  
    morrisTraversalPreorder(root); 
  
    printf("\n"); 
    preorder(root); 
  
    return 0; 
} 

Java

// Java program to implement Morris preorder traversal 
  
// A binary tree node 
class Node { 
      
    int data; 
    Node left, right; 
      
    Node(int item) { 
        data = item; 
        left = right = null; 
    } 
} 
  
class BinaryTree { 
      
    Node root; 
      
    void morrisTraversalPreorder() 
    { 
        morrisTraversalPreorder(root); 
    } 
  
    // Preorder traversal without recursion and without stack 
    void morrisTraversalPreorder(Node node) { 
        while (node != null) { 
  
            // If left child is null, print the current node data. Move to 
            // right child. 
            if (node.left == null) { 
                System.out.print(node.data + " "); 
                node = node.right; 
            } else { 
  
                // Find inorder predecessor 
                Node current = node.left; 
                while (current.right != null && current.right != node) { 
                    current = current.right; 
                } 
  
                // If the right child of inorder predecessor  
                // already points to this node 
                if (current.right == node) { 
                    current.right = null; 
                    node = node.right; 
                } 
   
                // If right child doesn't point to this node, then print 
                // this node and make right child point to this node 
                else { 
                    System.out.print(node.data + " "); 
                    current.right = node; 
                    node = node.left; 
                } 
            } 
        } 
    } 
      
    void preorder() 
    { 
        preorder(root); 
    } 
  
    // Function for Standard preorder traversal 
    void preorder(Node node) { 
        if (node != null) { 
            System.out.print(node.data + " "); 
            preorder(node.left); 
            preorder(node.right); 
        } 
    } 
      
    // Driver programs to test above functions 
    public static void main(String args[]) { 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(1); 
        tree.root.left = new Node(2); 
        tree.root.right = new Node(3); 
        tree.root.left.left = new Node(4); 
        tree.root.left.right = new Node(5); 
        tree.root.right.left = new Node(6); 
        tree.root.right.right = new Node(7); 
        tree.root.left.left.left = new Node(8); 
        tree.root.left.left.right = new Node(9); 
        tree.root.left.right.left = new Node(10); 
        tree.root.left.right.right = new Node(11); 
        tree.morrisTraversalPreorder(); 
        System.out.println(""); 
        tree.preorder(); 
          
    } 
} 
  
// this code has been contributed by Mayank Jaiswal 

Python3

# Python program for Morris Preorder traversal 
  
# A binary tree Node 
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
  
# Preorder traversal without  
# recursion and without stack 
def MorrisTraversal(root): 
    curr = root 
  
    while curr: 
        # If left child is null, print the 
        # current node data. And, update  
        # the current pointer to right child. 
        if curr.left is None: 
            print(curr.data, end= " ") 
            curr = curr.right 
  
        else: 
            # Find the inorder predecessor 
            prev = curr.left 
  
            while prev.right is not None and prev.right is not curr: 
                prev = prev.right 
  
            # If the right child of inorder 
            # predecessor already points to 
            # the current node, update the  
            # current with it's right child 
            if prev.right is curr: 
                prev.right = None
                curr = curr.right 
                  
            # else If right child doesn't point 
            # to the current node, then print this 
            # node's data and update the right child 
            # pointer with the current node and update 
            # the current with it's left child 
            else: 
                print (curr.data, end=" ") 
                prev.right = curr  
                curr = curr.left 
  
# Function for Standard preorder traversal 
def preorfer(root): 
    if root : 
        print(root.data, end = " ") 
        preorfer(root.left) 
        preorfer(root.right) 
          
  
# Driver program to test  
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
  
root.left.left = Node(4) 
root.left.right = Node(5) 
  
root.right.left= Node(6) 
root.right.right = Node(7) 
  
root.left.left.left = Node(8) 
root.left.left.right = Node(9) 
  
root.left.right.left = Node(10) 
root.left.right.right = Node(11) 
  
  
MorrisTraversal(root) 
print("\n") 
preorfer(root) 
  
  
# This code is contributed by 'Aartee' 

C#

// C# program to implement Morris 
// preorder traversal  
using System; 
  
// A binary tree node  
public class Node 
{ 
    public int data; 
    public Node left, right; 
  
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 
  
class GFG 
{ 
public Node root; 
  
public virtual void morrisTraversalPreorder() 
{ 
    morrisTraversalPreorder(root); 
} 
  
// Preorder traversal without  
// recursion and without stack  
public virtual void morrisTraversalPreorder(Node node) 
{ 
    while (node != null) 
    { 
  
        // If left child is null, print the  
        // current node data. Move to right child.  
        if (node.left == null) 
        { 
            Console.Write(node.data + " "); 
            node = node.right; 
        } 
        else
        { 
  
            // Find inorder predecessor  
            Node current = node.left; 
            while (current.right != null &&  
                   current.right != node) 
            { 
                current = current.right; 
            } 
  
            // If the right child of inorder predecessor  
            // already points to this node  
            if (current.right == node) 
            { 
                current.right = null; 
                node = node.right; 
            } 
  
            // If right child doesn't point to  
            // this node, then print this node  
            // and make right child point to this node  
            else
            { 
                Console.Write(node.data + " "); 
                current.right = node; 
                node = node.left; 
            } 
        } 
    } 
} 
  
public virtual void preorder() 
{ 
    preorder(root); 
} 
  
// Function for Standard preorder traversal  
public virtual void preorder(Node node) 
{ 
    if (node != null) 
    { 
        Console.Write(node.data + " "); 
        preorder(node.left); 
        preorder(node.right); 
    } 
} 
  
// Driver Code 
public static void Main(string[] args) 
{ 
    GFG tree = new GFG(); 
    tree.root = new Node(1); 
    tree.root.left = new Node(2); 
    tree.root.right = new Node(3); 
    tree.root.left.left = new Node(4); 
    tree.root.left.right = new Node(5); 
    tree.root.right.left = new Node(6); 
    tree.root.right.right = new Node(7); 
    tree.root.left.left.left = new Node(8); 
    tree.root.left.left.right = new Node(9); 
    tree.root.left.right.left = new Node(10); 
    tree.root.left.right.right = new Node(11); 
    tree.morrisTraversalPreorder(); 
    Console.WriteLine(""); 
    tree.preorder(); 
} 
} 
  
// This code is contributed by Shrikant13 

Javascript

<script> 
   
// Javascript program to implement Morris 
// preorder traversal  
  
// A binary tree node  
class Node 
{ 
  constructor(item) 
  { 
    this.data = item; 
    this.left = null; 
    this.right = null; 
  } 
} 
  
var root = null; 
  
  
// Preorder traversal without  
// recursion and without stack  
function morrisTraversalPreorder(node) 
{ 
    while (node != null) 
    { 
  
        // If left child is null, print the  
        // current node data. Move to right child.  
        if (node.left == null) 
        { 
            document.write(node.data + " "); 
            node = node.right; 
        } 
        else
        { 
  
            // Find inorder predecessor  
            var current = node.left; 
            while (current.right != null &&  
                   current.right != node) 
            { 
                current = current.right; 
            } 
  
            // If the right child of inorder predecessor  
            // already points to this node  
            if (current.right == node) 
            { 
                current.right = null; 
                node = node.right; 
            } 
  
            // If right child doesn't point to  
            // this node, then print this node  
            // and make right child point to this node  
            else
            { 
                document.write(node.data + " "); 
                current.right = node; 
                node = node.left; 
            } 
        } 
    } 
} 
  
  
// Function for Standard preorder traversal  
function preorder(node) 
{ 
    if (node != null) 
    { 
        document.write(node.data + " "); 
        preorder(node.left); 
        preorder(node.right); 
    } 
} 
  
// Driver Code 
root = new Node(1); 
root.left = new Node(2); 
root.right = new Node(3); 
root.left.left = new Node(4); 
root.left.right = new Node(5); 
root.right.left = new Node(6); 
root.right.right = new Node(7); 
root.left.left.left = new Node(8); 
root.left.left.right = new Node(9); 
root.left.right.left = new Node(10); 
root.left.right.right = new Node(11); 
morrisTraversalPreorder(root); 
document.write("<br>"); 
preorder(root); 
  
  
</script>

Output

1 2 4 8 9 5 10 11 3 6 7 
1 2 4 8 9 5 10 11 3 6 7

Time Complexity: O(n), we visit every node at most once.
Auxiliary Space: O(1), we use a constant amount of space for variables and pointers.

Limitations:
Morris’s traversal modifies the tree during the process. It establishes the right links while moving down the tree and resets the right links while moving up the tree. So the algorithm cannot be applied if write operations are not allowed.

This article is compiled by Aashish Barnwal and reviewed by the GeeksforGeeks team.

GeeksforGeeks

Improve

Previous Article

BFS vs DFS for Binary Tree

Iterative Preorder Traversal

Similar Reads

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver

Level order traversal of Binary Tree using Morris Traversal

Given a binary tree, the task is to traverse the Binary Tree in level order fashion.Examples: Input: 1 / \ 2 3 Output: 1 2 3 Input: 5 / \ 2 3 \ 6 Output: 5 2 3 6 Approach: The idea is to use Morris Preorder Traversal to traverse the tree in level order traversal.Observations: There are mainly two observations for the traversal of the tree using Mor

Reverse Morris traversal using Threaded Binary Tree

What is Morris traversal?Morris (InOrder) Traversal is a tree traversal algorithm that does not use recursion or stacks. This traversal creates links as descendants and outputs nodes using those links. Finally, undo the changes to restore the original tree.Given a binary tree, task is to do reverse inorder traversal using Morris Traversal. Prerequi

Correct BST whose two nodes are swapped (using Morris Traversal)

Given a Binary Search Tree with two of the nodes of the Binary Search Tree (BST) swapped. The task is to fix (or correct) the BST.Note: The BST will not have duplicates. Examples: Input Tree: 10 / \ 5 8 / \ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree. Following is the output tree 10 / \ 5 20 / \ 2 8 Approach: Traverse the

Morris traversal for Postorder

Perform Postorder Tree traversal using Morris Traversal. Examples: Input: 1 / \ 2 3 / \ / \ 6 7 8 9 Output: 6 7 2 8 9 3 1 Input: 5 / \ 2 3 / \ / \ 4 N 8 9 Output: 4 2 8 9 3 5 Approach: The approach to performing Morris Traversal for Postorder is similar to Morris traversal for Preorder except swapping between left and right node links. Create a vec

Convert Binary Tree to Doubly Linked List using Morris Traversal

Given a Binary Tree (BT), convert it to a Doubly Linked List (DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal must be the head node of the DLL. Examples: Input

Find postorder traversal of BST from preorder traversal

Given an array representing preorder traversal of BST, print its postorder traversal. Examples: Input : 40 30 35 80 100 Output : 35 30 100 80 40 Input : 40 30 32 35 80 90 100 120 Output : 35 32 30 120 100 90 80 40 Prerequisite: Construct BST from given preorder traversal Simple Approach: A simple solution is to first construct BST from a given preo

Construct BST from given preorder traversal using Stack

Given preorder traversal of a binary search tree, construct the BST.For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree. 10 / \ 5 40 / \ \ 1 7 50 We have discussed O(n^2) and O(n) recursive solutions in the previous post. Following is a stack based iterative solution that works in O(n) time

Modify a binary tree to get preorder traversal using right pointers only

Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers. Examples: Input : 10 / \ 8 2 / \ 3 5 Output : 10 \ 8 \ 3 \ 5 \ 2 Explanation : The preorder traversal of given binary tree is 10 8 3 5 2. Method

Find n-th node in Preorder traversal of a Binary Tree

Given a Binary tree and a number N, write a program to find the N-th node in the Preorder traversal of the given Binary tree. Prerequisite: Tree Traversal Examples: Input: N = 4 11 / \ 21 31 / \ 41 51 Output: 51 Explanation: Preorder Traversal of given Binary Tree is 11 21 41 51 31, so 4th node will be 51. Input: N = 5 25 / \ 20 30 / \ / \ 18 22 24

Article Tags :

DSA
Tree

Practice Tags :

Tree