Inorder traversal of BST without extra space

• binarysearchtree
• binarytree
• inordertraversal
•   
  subscribe

• Posted: 7 years ago

• Edit
• answers (1)
• views (5903)

 
Initialize current = root.
  While (current node is not null)
      If (Current node has no left child)
          Print current node's data.
          Go to its right child.
      else
          Make the current node as right child of the rightmost node in current's left subtree.
          Go to the left child.

 
public static void inOrderTraversalWOSpace(Node root) {
   if (root == null)
     return;

   Node previous, current;
   current = root;
   while (current != null) {
     if (current.left == null){
         System.out.println(current.data);
         current = current.right;
     }else{
         /* Find the inorder predecessor of current */
         previous = current.left;
         while (previous.right != null  & &  previous.right != current)
              previous = previous.right) ;

         /* Make current as right child of its inorder predecessor */
         if (previous.right == null) {
              previous.right = current;
              current = current.left;
         }else {
             /* Restore the original tree : Fix the right child of predecssor */
              previous.right = null;
              System.out.println(current.data);
              current = current.right;
         }
      }
   }
 }