fork(4) download
copy 
  1.  
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  4. /**
  5.  * Node Structre
  6.  * @author Prateek
  7.  *
  8.  */
  9. class Node {
  10. 	Node left;
  11. 	int data;
  12. 	Node right ;
  13.  
  14. 	public Node(int val){
  15. 		this.data=val;
  16. 	}
  17.  
  18. 	public String toString(){
  19. 		return this.data + "";
  20. 	}
  21. }
  22.  
  23. /**
  24.  * Binary Tree to DLL conversion
  25.  * @author Prateek
  26.  */
  27.  class BinaryToDLink {
  28.  
  29. 	/**
  30. 	 * Binary Tree to DLL (using QUeue)
  31. 	 * @param root
  32. 	 */
  33. 	public void changeToDLL(Node root){
  34.  
  35.               if(root==null)
  36.             	  return;
  37.  
  38.               Queue<Node> queue= new LinkedList<Node>();
  39.  
  40.               queue.offer(root);  //push 1st element
  41.  
  42.               Node parent =null;
  43.               Node child =null;
  44.  
  45.               while(!queue.isEmpty()){
  46.  
  47.             	  Node popedItem = queue.poll();
  48.             	  child = popedItem;
  49.  
  50.             	if(child.left!=null)
  51.             	 queue.offer(child.left) ;
  52.             	if(child.right!=null) 
  53.             	queue.offer(child.right) ;
  54.  
  55.             	 child.right = queue.peek();
  56.  
  57.             	 child.left = parent;
  58.             	 parent = child;
  59.               }
  60.  
  61.               printList(parent) ;
  62. 	}
  63.  
  64. 	public void printList(Node last){
  65. 		Node temp=last;
  66. 		while(temp!=null){
  67. 			System.out.print("  <---" +temp.data);
  68. 			temp=temp.left;
  69. 		}
  70. 	}
  71.  
  72. 	public static void main(String[] args) {
  73.         Node root = new Node(1) ;
  74.         root.left= new Node(2) ;
  75.         root.right= new Node(3) ;
  76.         root.left.left= new Node(4) ;
  77.         root.left.right= new Node(5) ;
  78.  
  79.      BinaryToDLink obj=  new BinaryToDLink();
  80.      obj.changeToDLL(root);
  81. 	}
  82.  
  83.  
  84. }
  85.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  <---5  <---4  <---3  <---2  <---1
https://ideone.com/XU6Wsk
language:
Java (12.0.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!