fork download
copy 
  1. class Node  {
  2. 	public Node left;
  3. 	public int data;
  4. 	public Node right;
  5.  
  6. 	public Node(int val){
  7. 		this.data=val;
  8. 	}
  9.  
  10. 	@Override
  11. 	public String toString(){
  12. 		return this.data + "";
  13. 	}
  14. }
  15.  
  16.  
  17.  
  18. /**
  19.  * Inorder Morris Traversal(Threaded Binary Concept used)
  20.  * @author Prateek
  21.  */
  22.  class InorderMorrisTraversal {
  23.  
  24. 	public void inorderMorrisTraversal(Node root){
  25.  
  26. 		if(root==null)
  27. 			return ;
  28.  
  29. 		Node current=root;
  30. 		while(current!=null){
  31.  
  32. 			if(current.left == null)
  33. 			{
  34. 				System.out.println(current.data); 
  35. 				current = current.right;
  36. 			}
  37. 			else
  38. 			{
  39. 				Node pre =  current.left;
  40. 				while(pre.right != null && pre.right!=current)
  41. 					pre = pre.right;
  42.  
  43. 				//pre = predessor of current node
  44.  
  45. 				if(pre.right==null) //make the link
  46. 				{
  47. 					pre.right = current ;
  48. 					current = current.left;
  49. 				}
  50. 				else //Break the link
  51. 				{
  52. 					pre.right = null ;
  53. 					System.out.println(current.data);
  54. 					current = current.right;
  55. 				}
  56. 			}
  57. 		}
  58. 	}
  59.  
  60. 	public static void main(String[] args) {
  61. 		InorderMorrisTraversal obj = new InorderMorrisTraversal();
  62.  
  63. 		Node root = new Node(12);
  64. 		root.left = new Node(8);
  65. 		root.left.left = new Node(6);
  66. 		root.left.left.right = new Node(7);
  67. 		root.left.right = new Node(10);
  68. 		root.left.right.left = new Node(9);
  69.  
  70. 		root.right = new Node(16);
  71. 		root.right.left = new Node(14);
  72. 		root.right.left.right = new Node(15);
  73. 		root.right.right = new Node(20);
  74. 		root.right.right.left = new Node(18);
  75.  
  76. 		System.out.println("Inorder Traversal is :");
  77. 		obj.inorderMorrisTraversal(root);
  78. 	}
  79. }
  80.  
Success #stdin #stdout 0.06s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder Traversal is :
6
7
8
9
10
12
14
15
16
18
20
https://ideone.com/f3lN0T
language:
Java (12.0.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!