Sunday, December 29, 2013

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 

No comments:

Post a Comment