Inorder Tree Traversal without recursion and without stack!

Solution:

• Its possible using Threaded Binary Tree

Algorithm:

• Iterate till node is not null,
  • get predecessor of node
  • if predecessor is null then
    • Print node
    • Move to right sub tree i.e. node = node.right
  • else if predecessor == node then
    • set predecessor.right = null
  • else if predecessor.right is null then,
    • Set predecessor.right = node
    • Set node = node.left

Latest Source Code:
Github: BinaryTreeInOrderTravelWithThread.java

Output:

       6               
      / \       
     /   \      
    /     \     
   /       \    
   13       8       
  / \     / \   
 /   \   /   \  
 1   5   7   11   
            / \ 
            9 3 
                                
1 13 5 6 7 8 9 11 3