Convert a Binary Search Tree to a Doubly Link List

/*
 * Convert a Binary Search Tree to a Doubly Link List
 * Reference: http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
 */
public class BST2DLL {
    TNode root = null;
 
    public BST2DLL(){
        root = null;
    }
 
    public BST2DLL(TNode t){
        root = t;
    }
 
    public TNode convertTree2DLL(TNode root){
        if(root == null)
            return root;
        if(root.left != null){
            TNode left = convertTree2DLL(root.left);
            for(;left.right != null; left = left.right);
            left.right = root;
            root.left = left;
        }
        if(root.right != null){
            TNode right = convertTree2DLL(root.right);
            for(;right.left != null; right=right.left);
            right.left = root;
            root.right = right;
        }
        return root;
    }
 
    public TNode BST2List(TNode root){
        if(root == null)
            return root;
        root = convertTree2DLL(root);
        while(root.left != null)
            root = root.left;
        return root;
    }
 
    public void printDLL(TNode root){
        System.out.print("\nList\t");
        for(;root!= null; root=root.right)
            System.out.print(root.data+" ");
        System.out.println();
    }
    public static void main(String args[]){
        //Create BST
        BinaryTree bt = new BinaryTree();
        bt.addNode(10);
        bt.addNode(8);
        bt.addNode(6);
        bt.addNode(9);
        bt.addNode(15);
        bt.addNode(12);
        bt.addNode(17);
        bt.inorder(bt.root);
     
        BST2DLL bd = new BST2DLL();
        TNode root = bd.BST2List(bt.root);
        bd.printDLL(root);
    }
}

#output

6 8 9 10 12 15 17 

List 6 8 9 10 12 15 17 

Level Order Traversal for Binary Tree

    public void levelTraversal(TNode root) {
        TNodeQueue queue = new TNodeQueue();
        if(root != null){
            queue.push(root);
            while(!queue.isEmpty()){
                //System.out.println("Queue: " + queue.isEmpty());
                TNode tmp = queue.pop();
                System.out.print(tmp.data + " ");
                if(tmp.left != null)
                    queue.push(tmp.left);
                if(tmp.right != null)
                    queue.push(tmp.right);
            }
        }
    }

# output

Inorder:

2 4 6 8 9 10 

Level Order Traversal: 

8 4 9 2 6 10 

Stack with TNode (Tree Node)

public class NodeStack {

    TNode stack[] = null;
    int top = 0;

    //int ssize = 0;
    NodeStack(int n) {
        stack = new TNode[n];
    }

    NodeStack() {
        stack = new TNode[100];
    }

    public boolean isEmpty() {
        if (top < 0) {
            return true;
        } else {
            return false;
        }
    }

    public void printPop() {
        System.out.println("Poppoed " + this.pop().data);
    }

    public void push(TNode p) {
        if (top < stack.length) {
            stack[top++] = p;
        }
        //System.out.println("Top: " + top);
    }

    public TNode top(){
        if(top>0)
            return stack[top-1];
        return null;
    }
    public TNode pop() {
        TNode p = null;
        if (top > 0) {
            p = stack[--top];
        }
        //System.out.println("Top: " + top);
        return p;
    }

    public void printStack() {
        System.out.print("Stack [LIFO order]: ");
        for (int i = this.top - 1; i >= 0; i--) {
            System.out.print(stack[i].data + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        NodeStack s = new NodeStack();
        s.push(new TNode(10));
        s.push(new TNode(15));
        s.push(new TNode(20));
        s.push(new TNode(25));
        s.printStack();
        s.printPop();
        s.printPop();
        s.push(new TNode(19));
        s.push(new TNode(24));
        s.printStack();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printPop();
        s.printStack();
    }
}

# output:

Stack [LIFO order]: 25 20 15 10 

Poppoed 25

Poppoed 20

Stack [LIFO order]: 24 19 15 10 

Poppoed 24

Poppoed 19

Poppoed 15

Poppoed 10

Stack [LIFO order]: 

Iterative or non-recursive version of Binary Tree Inorder, Preorder & Postorder

 public void nonRecursiveInorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            System.out.print(root.data + " ");
            root = root.right;
        }
    }

    public void nonRecursivePreorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while (root != null) {
                System.out.print(root.data + " ");
                s.push(root);
                //System.out.println()
                root = root.left;
            }
            if (s.isEmpty()) {
                break;
            }
            root = s.pop();
            if (root == null) {
                break;
            }
            root = root.right;
        }
    }

    public void nonRecursivePostorder(TNode root) {
        NodeStack s = new NodeStack(this.totNode);
        while (true) {
            while(root != null){
                if(root.right != null)
                    s.push(root.right);
                s.push(root);
                root = root.left;
            }
            if(s.isEmpty())
                break;
            root = s.pop();
            if(root == null)
                break;
            if(root.right != null && s.top() == root.right){
                s.pop();
                s.push(root);
                root = root.right;
            }else{
                System.out.print(root.data + " ");
                root = null;
            }
        }
    }

[Reference: http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/]

For TNode definition, please check my previous post.