/*
* 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);
}
}
* 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