CareerCup

Why can't people also give a brief description of the idea behind the code, instead of giving just the code?

f(n){
   if(n!=null){
      f(n->left)
      f(n->right)
      x=n->left
      if(x!=null){
           while(x->right)
                x=x->right
           x->right=n
      }
      n->left=x

      y=n->right
      if(y!=null){
          while(y->left)
              y=y->left
          y->left=n
      }
      n->right=y

      while(n->right!=null)
           n=n->right
   }
   return n
}

typedef struct bst{
int data;
node* left;
node* right;
}node

node* convert(node *root,bool right)
{ if(!root) return null;
node *pleft= null;
node *pright = null;
//linked the left sub-tree
if (root->pleft)
pleft = convert(root->pleft,flase);

//connect left subtree
if (pleft)
{
pleft->right = root;
root->left = pleft;
}

if(root->right)
pright = convert(root->right,true);

if(pright)
{
root->right = pright;
pright->left = root;
}

node* temp = root;

if (right)
{

while (temp->left)
temp=temp->left;
}
else
{while(temp->right)
temp=temp->right;
}
return temp;
}

first time call convert(&root,true);

connect(node *root){
node * tail;
if(root->left){
node* tail = root->next = root->left;
root->left->before = root;
}
if(root->right){
tail->next = tail->right;
tail->left->before = tail;
}
if(root->left){
connect(root->left);
}
if(root->right){
connect(root->right);
}

}

Guys this code is not as simple as it seems..!

This problem was solved by some folks at stanford. They claimed this to be one of the toughest problems in recursion and linkedlists.

Check this out...

http://cslibrary.stanford.edu/109/TreeListRecursion.pdf

Use Inorder Traversal ! At every print node statement instead of printing create a list node ! Use recursive Inorder Traversal !

// converts tree into doubly list and returns head
// next = right
// prev = left

static node_t *
toList(node_t *curr, node_t *next)
{
if (curr == 0) return next;

curr->right = toList(curr->right, next);
if (curr->right)
curr->right->left = curr;

return toList(curr->left, curr);
}

// invoke as below,

head = toList(root, 0);

bsttodll(root *root){
node *tail =null;

for(node *p=root;p;p=p->next){
node *q;
while(q=p->right){
p->right=q->left;
q->left=p
p=q;
} //end while

p->right=tail;
if(tail){
tail->left=p;
tail=p}

}//end for
return tail;
}

one way of doin this is....
1)convert the left subtree to a sorted linked list
2)convert the right subtree to a sortd linked list (hence recursive)
3)connect the root to the highest node in left subtree(go right until null)
4)connect the root to the lowest node in right subtree(go left until null)

1. traverse the tree inorder ( you get a single linked list in sorted order )
2. while traversing the tree inorder , maintain the links in such a way that you link ur current node with that of the previous node ( you get a double linked list in sorted order ) .

tree* convertBST2DLL(tree* bst, tree* current)
{
if (bst->left != NULL)
{
current = convertBST2DLL(bst->left, current);
}
if (current != NULL)
{
current->right = bst;
bst->left = current;
}
current = bst;
if (bst->right != NULL)
{
current = convertBST2DLL(bst->right, current);
}
return current;
}

http :// thermalnoise.wordpress . com/2008/05/24/binary-tree-comparison/

we can allocate an array of pointers, then go inorder and just write the address of each node into the array
so we have an array pointing at each node in the tree, and it's in a sorted way
all that's left is to decide if left means Prev or Next and connect em
like

<<connect first>>
for(i=1;i<n-1;i++)
{
a[i]->left=a[i-1];
a[i]->right=a[i+1];
}
<<connect last>>

del a;

easy enough?

the naive way would be for each node in the inorder traversal that we encounter, store it as a new node in a double linked array.

a better suggestion is :
let the left child symbolize pointer to previous node and right child symbolize pointer to next node.

1) have an inorder traversal
2) each time for a node with left child==null , point it to the predecessor ,
also go to the predecessor and change the right child to the predecessor to the current node.
3) each time for a node with right child==Null , point it to the successor. ( we cant change the pointers in this case since, we dont need to , the previous action would set thing right and even if we do it,it might affect our recursion.)

please let me know if i am wrong ..

I am sorry, we DO need to change the left child for the successors in the second case , but would it have an impact on our recursion .. wondering ...

use morris inorder traversal to convert BST to DLL.
Google it and u'll find I am posting the code....

void convert_bst_to_dll(node **root)
{
	node *p = *root;
	node *temp = NULL;
	node *ancestor = NULL;
	int set = 0;

	while(p != NULL)
	{
		if(p->lchild == NULL)
		{
			printf("%4d",p->data);
			if(set == 0)
			{
				*root = p;
				set = 1;
			}
			p->lchild = ancestor;
			if(ancestor)
				ancestor->rchild = p;
			p = p->rchild;
		}
		else
		{
			temp = p->lchild;
			while((temp->rchild != NULL) && (temp->rchild != p))
				temp = temp->rchild;
			if(temp->rchild == NULL)
			{
				temp->rchild  = p;
				p = p->lchild;
			}
			else
			{
				printf("%4d",p->data);
				//temp->rchild = NULL;
				p->lchild = temp;
				ancestor = p;
				p = p->rchild;
			}
		}
	}
	
}

node *toList(node* current, node* next)
{  
   if(current == NULL)   return next;
   
     current->right = toList(current->right, next);
     if(current->right)
       current->right->left = current;
     return( toList(current->left, currernt));
   }


}

private Node ConvertLL(Node root)
{
if (root == null)
return null;

Node rootNode = new Node(root.data);

rootNode.left = null;
rootNode.right = null;

if (root.left == null && root.right == null)
{
return rootNode; //Left Node
}


Node leftNode = ConvertLL(root.left);
Node rightNode = ConvertLL(root.right);

Node curNode = leftNode;
if(leftNode!=null)
while (curNode.right != null) //Move to the right end of the left segment
{
curNode = curNode.right;
}

Append(curNode, rootNode); //Append Left with currentRoot
Append(rootNode, rightNode); //Append currentRoot with Right

if (leftNode != null)
return leftNode;
else
return root;
}

private Node Append(Node NodeOne, Node NodeTwo)
{
if(NodeOne!=null)
NodeOne.right = NodeTwo;

if(NodeTwo!=null)
NodeTwo.left = NodeOne;

return NodeOne;
}

BST(node *h, Dlist ** l) {
    BST(h->left,l);
    if (!*l) {
        *l = (Dlist*)malloc(sizeof(*));
        (*l)->data = h->data;
        memset(*l, 0, sizeof(void*));
    } else {
        Dlist * t = (Dlist*)malloc(sizeof(Dlist));
        t->data = h->data;
        t->left = (*l);
        (*l)->right =t;
        // adjust the pointer 
        l =&t;
    }
    BST(h->right, l);
}
// end

BST(node *h, Dlist ** l) {
    BST(h->left,l);
    if (!*l) {
        *l = (Dlist*)malloc(sizeof(*));
        (*l)->data = h->data;
        memset(*l, 0, sizeof(void*));
    } else {
        Dlist * t = (Dlist*)malloc(sizeof(Dlist));
        t->data = h->data;
        t->left = (*l);
        (*l)->right =t;
        // adjust the pointer 
        l =&t;
    }
    BST(h->right, l);
}
// end

Node * ConvertBSTintoDoublyLinkList(Node *root)
{
if(root == NULL)
return NULL;
Node *leftSubTree = ConvertBSTintoDoublyLinkList(root->left);
Node *rightSubTree = ConvertBSTintoDoublyLinkList(root->right);

while((leftSubTree != NULL) && (leftSubTree->right != NULL))
leftSubTree=leftSubTree->right;
while((rightSubTree != NULL) && (rightSubTree->left != NULL))
rightSubTree = rightSubTree->left;

root->left= leftSubTree;
root->right = rightSubTree;

if(leftSubTree != NULL)
leftSubTree->right = root;
if(rightSubTree != NULL)
rightSubTree->left = root;

return root;
}

This is the simple code in java which 100% works

node convert(node n)
{
	if((n==null)||(n.left==null && n.right==null))
		return n;
	node n1=convert(n.left);
	node n2=convert(n.right);
	node n3=n1;
	while(n3.next!=null)
		n3=n3.next;
	n3.right=n;
	n.left=n3;
	n.right=n2;
	n2.left=n;
	return n1;
}

public static Node append(Node a, Node b) {
if either is null, return the other
if (a==null) return(b);
if (b==null) return(a);
find the last node in each using the .previous pointer
Node aLast = a.small;
Node bLast = b.small;
join the two together to make it connected and circular
join(aLast, b);
join(bLast, a);
return(a);
}

--Recursion--
Given an ordered binary tree, recursively change it into
a circular doubly linked list which is returned.

public static Node treeToList(Node root) {
base case: empty tree -> empty list
if (root==null) return(null);
Recursively do the subtrees (leap of faith!)
Node aList = treeToList(root.small);
Node bList = treeToList(root.large);
Make the single root node into a list length-1
in preparation for the appending
root.small = root;
root.large = root;
At this point we have three lists, and it's
just a matter of appending them together
in the right order (aList, root, bList)
aList = append(aList, root);
aList = append(aList, bList);
return(aList);
}

Here is my solution in C#:

Assume there is a Node class

public class Node
{
   Node Left;
   Node Right;
   Node Next;
   Node Previous;
}

and a linked list builder class

public class LinkedListBuilder
{
   public Node MinElement;
   public Node MaxElement;
}

Then you can create a linked list as follows:

private LinkedListBuilder CreateLinkedListInternal(Node root)
{
   if (root == null)
   {
      return null;
   }
   
   LinkedListBuilder result = new LinkedListBuilder{MinElement = root, MaxElement = root};

   if (root.Left != null)
   {
      LinkedListResult leftResult = CreateLinkedListInternal(root.Left);
      leftResult.MaxElement.Next = root;
      root.Previous = leftResult.MaxElement;
      result.MinElement = leftResult.MinElement;
   }

   if (root.Right != null)
   {
      LinkedListResult rightResult = CreateLinkedListInternal(root.Right);
      rightResult.MinElement.Previous = root;
      root.Next = rightResult.MinElement;
      result.MaxElement = rightResult.MaxElement;
   }

   return result;
}

public Node CreateLinkedList(Node root)
{
   LinkedListBuilder result = CreateLinkedListInternal(root);
   
   return (result != null) ? result.MinElement ? null;
}

void treeToDLL(Tree *root, Tree *last)
  {
    if (root)
    {
      treetoDLL(root->left, last);
      if (last)
        last->right = root;
      root->left = last;
      last = root;
      treetoDLL(root, last);
    }
  }

This will create a doubly linked list in place. The node's left property points to the previous node while the right property points to the next node. This approach is exactly like an in-order traversal except instead of printing out each node's value we replace that with logic that creates a double link between two nodes.

1) If the current node is null, return.

2) Recursively traverse the left nodes.

3) If the head of the linked list is null then make the current node the head (this will only happen once).

4) If the previous node is not null, make the current node's left property point to the previously traversed node. Then make the previously traversed node's right property point to the current node. Now the previous node and the current node are doubly linked.

5) Make the current node equal the previous node.

6) Recursively traverse the right nodes.

private void ToDoublyLinkedList(Node node, ref Node prev, ref Node head)
{
    if (node == null) return;
    ToDoublyLinkedList(node.Left, ref prev, ref head);
    if (head == null) head = node;
    if (prev != null)
    {
        node.Left = prev;
        prev.Right = node;
    }

    prev = node;
    ToDoublyLinkedList(node.Right, ref prev, ref head); 
}

public Node ToDoublyLinkedList()
{
    Node head = null;
    Node prev = null;
    ToDoublyLinkedList(_binarySearchTreeRoot, ref prev, ref head);
    return head;
}