Morris traversal for Preorder

Last Updated : 04 Nov, 2024

Given a Binary Tree, the task is to print its Preorder Traversal, without using recursion or stack.

Examples:

Input:
Output: 1 2 4 5 3
Explanation: Preorder traversal (Root->Left->Right) of the tree is 1 2 4 5 3
Input:
Output: 8 1 7 10 5 10 6 6
Explanation: Preorder traversal (Root->Left->Right) of the tree is 8 1 7 10 5 10 6 6

Approach:

Using Morris Preorder Traversal, we can traverse the tree without using a stack or recursion. The idea of Morris Traversal is inspired by the Threaded Binary Tree. In this traversal, we first establish links to the inorder predecessor and print the data using these links, and finally revert the changes to restore the original tree structure. Although the tree is temporarily modified during the traversal, it is reverted back to its original shape after completion.

The algorithm for Preorder is almost similar to Morris traversal for Inorder.

Initialize the current node as the root of the binary tree.
If the left child of the current node is NULL, print the current node's value and move to its right child.
If the left child exists, find the rightmost node in the left subtree (inorder predecessor) of the current node.
Establish Links:
- If the right child of the inorder predecessor points to the current node, it indicates that the left subtree has been visited. Set the right child of the predecessor to NULL and move to the right child of the current node.
- If it doesn't point to the current node, print the current node's value, set the predecessor's right child to the current node (to create a temporary link), and move to the left child.
Continue this process until the current node becomes NULL, effectively visiting all nodes in preorder without using additional space for a stack or recursion.

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; 
	Node(int x){
      	data = x;
      	left = right = nullptr;
    }
}; 

// Preorder traversal without recursion and without stack 
void preOrder(Node* root) { 
    while (root)  { 
        
      	// If left child is null, print the 
      	// current node data. Move to  right child. 
        if (root->left == nullptr)  { 
            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 = nullptr; 
                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; 
            } 
        } 
    } 
} 

int main()  { 
  
    // Constructing binary tree.
    //
    //             1
    //            / \
    //           /   \
    //          2     3
    //         / \   / \
    //        /   \ /   \
    //       4    5 6    7
    Node* 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);

    preOrder(root); 
    cout<<endl; 
  
    return 0; 
}

// C++ program for Morris Preorder traversal 

#include <stdio.h>
#include <stdlib.h>

struct Node { 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 


// Preorder traversal without recursion
// and without stack 
void preOrder(struct Node* root) { 
    while (root != NULL) { 
      
        // 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 != NULL && 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; 
            } 
        } 
    } 
} 

struct Node* newNode(int x) {
    struct Node* node = 
      	(struct Node*)malloc(sizeof(struct Node));
    node->data = x;
    node->left = node->right = NULL;
    return node;
}

int main() { 
  
    // Constructing binary tree.
    //
    //             1
    //            / \
    //           /   \
    //          2     3
    //         / \   / \
    //        /   \ /   \
    //       4    5 6    7
    struct Node* 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);

    preOrder(root); 
    printf("\n"); 

    return 0; 
}

Java

// Java program for Morris Preorder traversal

class Node {
    int data;
    Node left, right;

    Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {
  
    // Preorder traversal without recursion and without
    // stack
    static void preOrder(Node root) {
        while (root != null) {
          
            // If left child is null, print the current node
            // data. Move to right child.
            if (root.left == null) {
                System.out.print(root.data + " ");
                root = root.right;
            }
            else {
              
                // Find inorder predecessor
                Node current = root.left;
                while (current.right != null
                       && 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 {
                    System.out.print(root.data + " ");
                    current.right = root;
                    root = root.left;
                }
            }
        }
    }
    public static void main(String[] args) {
      
        // Constructing binary tree.
        //
        //             1
        //            / \
        //           /   \
        //          2     3
        //         / \   / \
        //        /   \ /   \
        //       4    5 6    7
        Node 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);

        preOrder(root);
        System.out.println();
    }
}

Python

# Python program for Morris Preorder traversal

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None


def preOrder(root):
    while root:
      
        # If left child is null, print the current 
        # node data. Move to right child.
        if root.left is None:
            print(root.data, end=" ")
            root = root.right
        else:
          
            # Find inorder predecessor
            current = root.left
            while current.right and current.right != root:
                current = current.right

            # If the right child of inorder predecessor
            # already points to this node
            if current.right == root:
                current.right = None
                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:
                print(root.data, end=" ")
                current.right = root
                root = root.left


if __name__ == "__main__":

    # Constructing binary tree.
    #
    #             1
    #            / \
    #           /   \
    #          2     3
    #         / \   / \
    #        /   \ /   \
    #       4    5 6    7
    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)

    preOrder(root)
    print()

// C# program for Morris Preorder traversal

using System;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {
  
    // Preorder traversal without recursion and without
    // stack
    static void preOrder(Node root) {
        while (root != null) {
          
            // If left child is null, print the current node
            // data. Move to right child.
            if (root.left == null) {
                Console.Write(root.data + " ");
                root = root.right;
            }
            else {
              
                // Find inorder predecessor
                Node current = root.left;
                while (current.right != null
                       && 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 {
                    Console.Write(root.data + " ");
                    current.right = root;
                    root = root.left;
                }
            }
        }
    }
    static void Main() {
      
        // Constructing binary tree.
        //
        //             1
        //            / \
        //           /   \
        //          2     3
        //         / \   / \
        //        /   \ /   \
        //       4    5 6    7
        Node 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);

        preOrder(root);
        Console.WriteLine();
    }
}

JavaScript

// JavaScript program for Morris Preorder traversal

class Node {
    constructor(x) {
        this.data = x;
        this.left = this.right = null;
    }
}

function preOrder(root) {
    while (root) {
    
        // If left child is null, print 
        // the current node data. Move to right child.
        if (root.left === null) {
            console.log(root.data + " ");
            root = root.right;
        }
        else {
        
            // Find inorder predecessor
            let 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 {
                console.log(root.data + " ");
                current.right = root;
                root = root.left;
            }
        }
    }
}

const 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);

preOrder(root);
console.log();

Output

1 2 4 5 3 6 7

Time Complexity: O(n), we visit every node at most once.
Auxiliary Space: O(1)

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 right operations are not allowed.