Coding Recipies: Binary Tree to Doubly Linked List

30 Oct 2013

Binary Tree to Doubly Linked List

Problem Statement:
Convert the given binary tree to Doubly Linked List(DLL)
Given Binary Tree is :

Resultant Doubly Linked List (DLL) of the given binary Tree:

Solution:

Node Structure in Linked List

 class LinkNode {  
      LinkNode prev;  
      int data;  
      LinkNode next ;  
 }

Node structure in a Binary Tree

 class BNode {  
      BNode left ;  
      int data;  
      BNode right;  
 }

The above basic structure of Node in a Binary Tree and DLL seems to be quite similar, implying a possibility of converting Tree Structure to DLL with few pointer manipulation.

From the above fig we see that the nodes in the DLL are in BFS traversal of the Tree, we already know that BFS traversal of Tree can be done with the help of Queue.

Concept:
Connect all the nodes in the queue as they we pushed while BFS traversal with right pointer , and backward linking is done by maintaing parent and child pointers to use up left pointer of the node.

Refer to Full Source Code

/**
  * Binary Tree to DLL (using QUeue)
  * @param root
  */
 public void changeToDLL(Node root){
            
              if(root==null)
               return;
              
              Queue<Node> queue= new LinkedList<Node>();
              
              queue.offer(root);  //push 1st element
              
              Node parent =null;
              Node child =null;
              
              while(!queue.isEmpty()){
               
               Node popedItem = queue.poll();
               child = popedItem;
               
             if(child.left!=null)
              queue.offer(child.left) ;
             if(child.right!=null) 
             queue.offer(child.right) ;
              
              child.right = queue.peek();
             
              child.left = parent;
              parent = child;
              }
              
              printList(parent) ;
 }
 
 public void printList(Node last){
  Node temp=last;
  while(temp!=null){
   System.out.print("  <---" +temp.data);
   temp=temp.left;
  }