how to convert binary search tree traversal recursion into non-recursive method in java

Question

Forgive me if its asked before but i couldn't find appropriate answer. I have an major issue in converting binary search tree traversal written with recursive method into non recursive method. kindly help me out. Here is a code using recursive method in java.

//BinarySt class

public interface BinaryST {
public void insert(Integer nData);
public Integer remove(Integer nData);
public boolean isExist(Integer nData);

public String preOrder();
public String inOrder();
public String postOrder();

}

//BinaryTreeNode class

public class BinaryTreeNode {
Integer element;
BinaryTreeNode LChild;
BinaryTreeNode RChild;

BinaryTreeNode() {}
}

//BinarySearchTree implements BinaryST class

public class BinarySearchTree implements BinaryST{
protected StringBuffer s;
protected BinaryTreeNode root;

public BinarySearchTree() {}        
public BinarySearchTree(Integer nData)
{
    root = new BinaryTreeNode();
    root.element = nData;
}

public void insert(Integer nData)
{
    if( root==null ) {
        root = new BinaryTreeNode();
        root.element = nData;
        return;
    }

    boolean flag=true;
    BinaryTreeNode c=root;

    while(flag) {
        if( nData>=c.element ) {
            if( c.RChild==null ) {
                c.RChild = new BinaryTreeNode();
                c.RChild.element = nData;
                flag = false;
            }
            c = c.RChild;
        } 
        else {
            if( c.LChild==null ) {
                c.LChild = new BinaryTreeNode();
                c.LChild.element = nData;
                flag = false;
            }
            c = c.LChild;
        }
    }
}

public Integer remove(Integer nData)
{
    return new Integer(5);
}

public boolean isExist(Integer nData)
{
    return true;
}

public String preOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    prOrder( root );

    return new String(s);
}

public String inOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    iOrder( root );

    return new String(s);
}

public String postOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    poOrder( root );

    return new String(s);
}

private void prOrder(BinaryTreeNode t) {
    if( t!=null ) {
        s.append( t.element.toString() + " " );
        prOrder( t.LChild );
        prOrder( t.RChild );
    }
}

private void iOrder(BinaryTreeNode t) {
    if( t!=null ) {
        iOrder( t.LChild );
        s.append( t.element.toString() + " " );
        iOrder( t.RChild );
    }
}

private void poOrder(BinaryTreeNode t) {
    if( t!=null ) {
        poOrder( t.LChild );
        poOrder( t.RChild );
        s.append( t.element.toString() + " " );
    }
}
}

//Runner class

public class Runner {
public static void main(String[] args) {
    BinarySearchTree a = new BinarySearchTree();

    System.out.println( "Pre-Order : "+a.preOrder() );
    System.out.println( "In-Order  : "+a.inOrder() );
    System.out.println( "Post-Order: "+a.postOrder() );

    a.insert( (Integer) 100 );
    a.insert( (Integer) 50  );
    a.insert( (Integer) 150 );
    a.insert( (Integer) 25  );
    a.insert( (Integer) 75  );
    a.insert( (Integer) 125 );
    a.insert( (Integer) 175 );
    a.insert( (Integer) 60  );
    a.insert( (Integer) 160 );
    a.insert( (Integer) 200 );
    a.insert( (Integer) 155 );

    System.out.println( "Pre-Order : "+a.preOrder() );
    System.out.println( "In-Order  : "+a.inOrder() );
    System.out.println( "Post-Order: "+a.postOrder() );
}
}

possible duplicate of [Post order traversal of binary tree without recursion](http://stackoverflow.com/questions/1294701/post-order-traversal-of-binary-tree-without-recursion) or [recursive and non resursive traversal of tree](http://stackoverflow.com/questions/15587177/recursive-and-non-resursive-traversal-of-tree) — Ted Hopp, Apr 18 '14 at 20:08
Generally, to convert a recursive algorithm into non-recursive, you need some sort of stack or linked list to keep track of where you've been. In some cases for, eg, a tree traversal algorithm you can use space that already exists (or can be allocated) in the nodes you're traversing. — Hot Licks, Apr 18 '14 at 20:14
with stack it is not working, so many errors in it. please help me — user3536823, Apr 19 '14 at 10:14

score 0 · Answer 1 · answered Apr 27 '14 at 04:59

This is code for preorder. Use this and convert into postorder and inorder

private void prOrder(BinaryTreeNode t) {
        if( t!=null ) {
            Stack<BinaryTreeNode> rootStack=new Stack<BinaryTreeNode>();
            BinaryTreeNode current=t;

            do{     
                s.append( current.element.toString() + " " );
                if(current.RChild!=null)
                    rootStack.add(current.RChild);
                if(current.LChild!=null)
                    rootStack.add(current.LChild);

                if(rootStack.isEmpty())
                    current=null;
                else
                    current=rootStack.pop();

            }while(current!=null);  

        }
    }

score 0 · Answer 2 · answered Nov 08 '14 at 15:42

Let Consider Binary Tree Node :

public class BinaryTreeNode {

private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode() {
}

public BinaryTreeNode(int data) {
    this.data=data;
}

public int getData() {
    return data;
}
public void setData(int data) {
    this.data = data;
}
public BinaryTreeNode getLeft() {
    return left;
}
public void setLeft(BinaryTreeNode left) {
    this.left = left;
}
public BinaryTreeNode getRight() {
    return right;
}
public void setRight(BinaryTreeNode right) {
    this.right = right;
}

}

Non Recusive Post order travesal :

public static void nonRecursivePostOrder(BinaryTreeNode root){

    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
    List<BinaryTreeNode> returnNodes = new LinkedList<BinaryTreeNode>();


      while (true) {
          if (root != null) {

              if (returnNodes.contains(root)) {
                  returnNodes.add(stack.pop());
                  root = null;
              } else {
                  stack.push(root);
                  root = root.getLeft();
              }

          } else {
              if (stack.isEmpty()) {
                  break;
              } else if (stack.peek().getRight() == null) {
                  root = stack.pop();
                  returnNodes.add(root);
                  if (root == stack.peek().getRight()) {
                      returnNodes.add(stack.pop());
                  }
              }

              if (!stack.isEmpty()) {
                  root = stack.peek().getRight();
              } else {
                  root = null;
              }
          }
      }

      for(BinaryTreeNode node : returnNodes)
          System.out.print(node.getData()+" ");

}

Non Recusive Inorder Travesal :

public static void nonRecursiveInOrder(BinaryTreeNode root){

    if(root == null)return;

    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();


    while (true) {

        if(root.getLeft()!=null){
            stack.push(root);               
            root = root.getLeft();
        }else if(root.getRight()!=null){
            System.out.print(root.getData()+" ");
            root = root.getRight();
        }else{
            System.out.print(root.getData()+" ");

            if(stack.isEmpty())
                break;

            root = stack.pop();
            System.out.print(root.getData()+" ");
            root = root.getRight();
        }



    }
}

Non Recursive PreOrder Traversal :

public static void nonRecursivePreOrder(BinaryTreeNode root){

    if(root == null)return;

    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();


    while (true) {

        if(root.getLeft()!=null){
            stack.push(root);
            System.out.print(root.getData()+" ");
            root = root.getLeft();
        }else if(root.getRight()!=null){
            System.out.print(root.getData()+" ");
            root = root.getRight();
        }else{
            System.out.print(root.getData()+" ");

            if(stack.isEmpty())
                break;
            root = stack.pop();
            root = root.getRight();
        }



    }
}

how to convert binary search tree traversal recursion into non-recursive method in java

2 Answers2