CODEWITHSUNDEEP
crecursionbinary-treedoubly-linked-list
david
david

Reputation: 57

How to convert Doubly linked list to Binary tree

    struct cnode
{
  int info;
  struct cnode *next;
  struct cnode *previous;
};
typedef struct cnode cnode;

pre-made DOUBLY LINKED LIST: 1<->2<->3<->4<->5<->6<->7

So I'm trying to make a recursive function that grabs the mid of the doubly linked list (root = 4) and convert it into a the remaining into a binary tree. I'm still new to recursion so an explanation along with code would be GREATLY appreciated!

EX.     4
      /  \
     2    6
    / \  / \
   1   3 5  7

This is the code I have thus far (which isn't much due to difficulties with recursion)

void *convert(cnode *head){
  if(head == NULL)
    return;
  int count = 0;
  cnode *tempHead = head;
  while(tempHead != NULL){
    count++;
    tempHead = tempHead->next;
  }
  int move = (count/2) + (count%2);
  int i;
  for(i=1; i<move; i++){
    head = head->next;
  }
}

Pretty much just sets the head pointer to the mid info (4)

Upvotes: 1

Views: 3871

Answers (3)

sgeeks
sgeeks

Reputation: 11

I hope this code will help you. call the DLL2BT method with head of the doubly linked list which return the root node of the tree created.

class box
{
    int data;
    box left=null,right=null;
    box(int a)
    {
        data=a;
    }
}

public static box DLL2BT(box head)// head = linked list head
{       
    if(head!=null)
    {
        box node=null;
        try 
        {
            node = findMid(head);
            node.left.right=null;
            node.left=DLL2BT(head);
            node.right.left=null;
            node.right=DLL2BT(node.right);
        }
        catch( Exception e){ }
        return node;
    }
    return null;
}

public static box findMid(box head)
{
    box slow=head,fast=head.right;
    try
    {
        while(fast!=null)
        {
            slow=slow.right;
            fast=fast.right.right;
        }
    }
    catch(Exception e){ }
    return slow;
}

Upvotes: 1

shiwang
shiwang

Reputation: 160

Firstly, You are trying to convert DLL to binary tree assuming the DLL is given as in-order of the binary tree you have to make. Note that there isn't a unique tree you can make from only inorder traversal.Even if you have to make BST, you can't make it with only inorder traversal. What I actually think you are trying to do is to convert it into a balanced BST. Even though, it will also not be unique.
Here's the algorithm..
1) Get the Middle of the linked list and make it root.
2) Recursively do same for left half and right half.
  a) Get the middle of left half and make it left child of the root created in step 1.
  b) Get the middle of right half and make it right child of the root created in step 1.
Time complexity: O(nLogn) where n is the number of nodes in Linked List.
Although,it can be solved in O(n) if you insert nodes in BST in the same order as the appear in Doubly Linked List.

Upvotes: 0

Prune
Prune

Reputation: 77910

I think I understand; you're making a balanced binary tree from cnodes with the previous and next pointers being reused for the left and right sub-trees.

... so that's your algorithm.

  • Find the middle node of the binary tree (which you've already done).
  • Turn the left half into a binary tree. The left half is the original head, with the last element (middle->previous) now having a next pointer of NULL.
  • Link this left half to middle->previous (hijacked as the left sub-tree).

  • Turn the right half into a binary tree; this is headed by middle->next. Make it the new value of middle->next.

  • You have to keep the original head as the pointer to the left sub-tree.

  • You'll want your routine to return the binary tree's root, so the previous call can link it into the level above.
  • You still have to pick a termination condition, such as the head pointer being NULL.

Does that get you moving to a solution?

Upvotes: 1

Related Questions