Morris Traversal for Preorder in Java

Without the use of recursion or stacks, we traverse a tree using the Morris algorithm. The linked binary tree is the foundation of the Morris traversal.

Preorder Morris Traversal Algorithm

The preorder Morris traversal algorithm, which is nearly identical to the inorderMorris traversal, is given below.

1. Move on to the right child after displaying the contents of the current node if indeed the left child is null.

Otherwise, check to make sure the correct child of the in-order predecessor is directed at the current node.

Two situations are involved:

• If the right child of both the inorder predecessor is pointing to the current node, set that child to NULL and move on to the right child of the current node.
• Set the right child of both inorder predecessors that are pointing to the current node to NULL and then proceed on to the right child of the current node if necessary.

2. Repeat if and only if the present node is not NULL.

Features

Due to the algorithm's resemblance towards the Morris traverse for the inorder, time complexity. Thus, O represents the program's overall time complexity (n).

Preorder traversal using a recursive technique is stated to not take up any space in several locations. This is untrue, though. Even if we don't explicitly offer the stack, recursion uses one.

The internal alteration made to the binary tree allows the Morris traversal to function. The Morris traversal never functions without internal change. Therefore, one should take care of the Morris traversal if the internal alteration is not permitted.

Program 1: For the Morris traversal preorder in java

import java.io.*;
import java.util.*;
class BTreeNode
{  
int val;
BTreeNodelt, rt;   
BTreeNode(int item)  
{  
val = item;  
lt = rt = null;  
}  
}  
public class BTree1   
{  
BTreeNode rt;  
void morrisTrvrslPreorder(BTreeNode r)   
{  
while (r != null)   
{  
if (r.lt == null)   
{  
System.out.print(r.val + " ");  
r = r.rt;  
}   
else   
{  
BTreeNodecurr = r.lt;  
while (curr.rt != null &&curr.rt != r)   
{  
curr = curr.rt;  
}  


if (curr.rt == r)   
{  
curr.rt = null;  
r = r.rt;  
}  
else   
{  
System.out.print(r.val + " ");  
curr.rt = r;  
r = r.lt;  
}  
}  
}  
}  


public static void main(String argvs[])  
{  
BTree tree = new BTree();  
tree.rt = new BTreeNode(6);  
tree.rt.lt = new BTreeNode(8);  
tree.rt.rt = new BTreeNode(9);  
tree.rt.lt.lt = new BTreeNode(1);  
tree.rt.lt.rt = new BTreeNode(4);  
tree.rt.rt.rt = new BTreeNode(7);  
tree.rt.lt.rt.lt = new BTreeNode(5);  
System.out.print("The inorder traversal of the binary tree is: \n" );  
tree.morrisTrvrslPreorder(tree.rt);  
}  
}   

The output of the above program

The inorder traversal of the binary tree is: 
6 8 1 4 5 9 7

Program 2: For the Morris traversal preorder in java

// Binary Tree Node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Define node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Root's starting value should be set.
this.root = null;
}
//  Recursive procedure
//Display the binary tree's preorder view.
public void preorder(TreeNode node)
{
if (node != null)
{
// Display node value
System.out.print("  " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// preorder tree traversal that is iterative
public void morrisPreorder()
{
if (this.root == null)
{
return;
}
TreeNode current = this.root;
TreeNode auxiliary = null;
// tree nodes being iterated
while (current != null)
{
if (current.left == null)
{
// display node value
System.out.print("  " + current.data);
// Visit the right children
current = current.right;
}
else
{
auxiliary = current.left;


                // Locate the rightmost node that is not 
                // similar to the current node
while (auxiliary.right != null &&
auxiliary.right != current)
{
auxiliary = auxiliary.right;
}
if (auxiliary.right != current)
{
// display node value
System.out.print("  " + current.data);
// Link the current node to the rightmost right node.
auxiliary.right = current;
current = current.left;
}
else
{      
auxiliary.right = null;
current = current.right;
}
}
}
System.out.print("\n");
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(-3);
tree.root.right.left = new TreeNode(7);
tree.root.left.right = new TreeNode(6);
tree.root.let.right.left = new TreeNode(9);
System.out.println("\n Recursive Preorder");
tree.preorder(tree.root);
System.out.println("\n Morris Preorder");
tree.morrisPreorder();
}
}

The output of the above program

Recursive Preorder
4  8  1  6  9  10  7  -3
 Morris Preorder
4  8  1  6  9  10  7  -3