Inorder Tree Traversal without recursion and without stack ! | A binary tree tNode has data , a pointer to left child and a pointer to right child ; Function to traverse a binary tree without recursion and without stack ; Find the inorder predecessor of current ; Make current as right child of its * inorder predecessor ; Revert the changes made in the ' if ' part to restore the original tree i . e . , fix the right child of predecessor ; Driver Code ; Constructed binary tree is 1 / \ 2 3 / \ 4 5
class tNode { int data ; tNode left , right ; tNode ( int item ) { data = item ; left = right = null ; } } class BinaryTree { tNode root ; void MorrisTraversal ( tNode root ) { tNode current , pre ; if ( root == null ) return ; current = root ; while ( current != null ) { if ( current . left == null ) { System . out . print ( current . data + " ▁ " ) ; current = current . right ; } else { pre = current . left ; while ( pre . right != null && pre . right != current ) pre = pre . right ; if ( pre . right == null ) { pre . right = current ; current = current . left ; } else { pre . right = null ; System . out . print ( current . data + " ▁ " ) ; current = current . right ; } } } } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new tNode ( 1 ) ; tree . root . left = new tNode ( 2 ) ; tree . root . right = new tNode ( 3 ) ; tree . root . left . left = new tNode ( 4 ) ; tree . root . left . right = new tNode ( 5 ) ; tree . MorrisTraversal ( tree . root ) ; } }