Morris Traversal for Inorder in Java

Through Morris’s traversal, a tree is traversed without the aid of recursion or stacks. Based on the threaded binary tree, the Morris traversal is used. We perform internal modification throughout this traverse to establish internal links for the in-order successor. We have eventually undone the alteration to bring back the original tree.

Algorithm for Morris Traversal in Order

The Morris Traversal involves the steps listed below (in Inorder).

1. Make the current node the root initially.
2. when the current does not equal zero

If the left child is absent from the current node

1. Show the data for the active node.
2. Visit the current node's right node by using the formula curr = curr -> right.

however, or else

1. The right-hand node in the currently left subtree should be sought out.

OR

which node's right child is the active node.

If a right child equals the current node 

1. Undo the modifications. Therefore, that right child should indeed be made to be NULL.

a node whose current node is its right child

1. Show the data for the active node.
2. Visit the right node by using the formula curr = curr -> right.

however, or else

1. Making the current node the right child of both the detected rightmost node is appropriate; and
2. Visit the curr = curr -> left child node.

Time Complexity: We note that the tree's edges are only crossed a maximum of three times. In the output tree, an equal amount of extra edges are formed and eliminated. As a result, the above program's overall time complexity is O(n).

Many places claim that the inorder traversal using a recursive technique doesn't take up any space. 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.

Program 1: For Morris traversal for inorder in java

class BTreeNode
{  
int val; 
BTreeNodelt, rt;   
BTreeNode(int item)  
{  
val = item;  
lt = rt = null;  
}  
}  


public class BTree
{  
BTreeNode rt; 
void MorrisTraversalInorder(BTreeNode rt)  
{  
BTreeNodecurr, pr;  
if (rt == null)  
{  
return;  
}  
curr = rt;  
while (curr != null)  
{  
if (curr.lt == null)  
{  
System.out.print(curr.val + " ");  
curr = curr.rt;  
}  
else   
{  
pr = curr.lt;  
while (pr.rt != null &&pr.rt != curr)  
{  
pr = pr.rt;  
}  
if (pr.rt == null)   
{  
pr.rt = curr;  
curr = curr.lt;  
} 
else  
{  
pr.rt = null;  
System.out.print(curr.val + " ");  
curr = curr.rt;  
} 
}   
}   
}  
public static void main(String argvs[])  
{  


//                        6  
//                      /   \  
//          8    9  
//                  /   \       \  
//                1      4      7  
//                       /  
//                    5  


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.MorrisTraversalInorder(tree.rt);  
}  
}  

The output of the above program

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

Program 2: For Morris traversal for inorder 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 approach
// Display the binary tree in order.
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
// Display node value
System.out.print("  " + node.data);
inorder(node.right);
}
}
// traversal of trees iteratively in order
public void morrisInorder()
{
if (this.root == null)
{
return;
}
// start at the tree's root node
TreeNode current = this.root;
TreeNode auxiliary = null;
// tree nodes iterative
while (current != null)
{
if (current.left == null)
{
// Node value to print
System.out.print("  " + current.data);
// Visit the right child when the left child is vacant.
current = current.right;
}
else
{
auxiliary = current.left;
while (auxiliary.right != null &&auxiliary.right != current)
{
auxiliary = auxiliary.right;
}
if (auxiliary.right != current)
{
// alter link
auxiliary.right = current;
current = current.left;
}
else
{
// Display node value
System.out.print("  " + current.data);
// Unlink
auxiliary.right = null;
// Visit to the right child
current = current.right;
}
}
}
System.out.print("\n");
}
public static void main(String[] args)
{
// make a new tree
BinaryTree tree = new BinaryTree();
// build a binary tree
/*  


         4
       /   \
      8     3
     / \   / \
    1   6 7   2
       /  
      9    
*/
//Nodes should be added to the tree
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(8);
tree.root.left.left = new TreeNode(1);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(7);
tree.root.left.right = new TreeNode(6);
tree.root.left.right.left = new TreeNode(9);
System.out.println("\n Recursive Inorder");
// Display inorder element
tree.inorder(tree.root);
System.out.println("\n Morris Inorder");
tree.morrisInorder();
}
}

The output of the above program

Recursive Inorder
1  8  9  6  4  7  3  2
 Morris Inorder
1  8  9  6  4  7  3  2