Tuesday, January 13, 2015

Java Code to Convert Binary Tree to Circular Doubly Linked List

/*
This function processes Binary Tree as show below
                               1
                 2                           3
      4                5
to circular doubly linked list as shown


4 <-> 2 <-> 5 <-> 1 <-> 3

Also links to 4 and 3 are updated.
*/

public void convertBTToCDLL(Node current, Node toReturnHead, Node toReturnTail)
{
    // Exit conditions and Null handling here.
    if( current == null )
    {
        return;
    }
   
    // convert left sub tree to CDLL
    Node leftSubTreeHead=null;
    Node leftSubTreeTail=null;
    if( current->left )
    {
        convertBTToCDLL(current->left, leftSubTreehead, leftSubTreeTail);
    }
   
    // convert right sub tree to CDLL
    Node rightSubTreeHead=null;
    Node rightSubTreeTail=null;
    if(current->right)
    {
        convertBTToCDLL(current->right, rightSubTreeHead, rightSubTreeTail);
    }
  
    // Convert the current node to CDLL 
    if(! leftSubTreeTail)
    {
        leftSubTreeTail = leftSubTreeHead = current;
  
    }
       
    if(! rightSubTreeHead)
    {
        rightSubTreeHead = rightSubTreeTail = current;
    }


    leftSubTreeTail->right = current;
    current->left = leftSubTreeTail;

    rightSubTreeHead->left = current;
    current->right = rightSubTreeHead;

    // Make this circular
    toReturnHead = leftSubTreeHead;
    toReturnTail = rightSubTreeTail;
}

No comments:

Post a Comment