CareerCup

You are right.
Inorder traversal would give a sorted list which can be pused inside a circular link list.

-to Neo : How BFS would work? elements will nto be in sorting order in that case.

We can Insert elements in link list by traversing tree in INORDER. At last we can point last elemtents node to the head.

Guys,

1) Inorder traversal of a Binary search Tree prints the data in the increasing order.
2) While doing inorder traversal, at each step, build the linked list adding the each element at the end of linked list.
3) At each step, also make the end of the linked list to point to the first element of the linked list.

Basically, we need to maintain always two pointers, one to head and another to the last element of the linked list

its the great tree list recursion problem... find it on
http://www.google.com/search?hl=en&q=stanford+cs+lib&btnG=Search

void main_class::iterate(Node *new_node)
{	
	char flag;
	Node *temp_parent = NULL;
	if (root == NULL)
	{
		//This is the root node
		root = new_node;
		cout<<"Root value: "<<root->value<<"\n\n";
	}
	else
	{
		//This is not a root node and hence, now we iterate
		Node *current = root;
		
		while(current != NULL)
		{
			if(current->value < new_node->value)   // Go right
			{
				temp_parent = current;
				current = current->child_right;
				flag = 'r';
			
			}
			else
			{
				temp_parent = current;
				current = current->child_left;
				flag = 'l';
			
			}
		}

		new_node->parent = temp_parent;
		if(flag == 'l')
		{
			temp_parent->child_left = new_node;
		}
		else
		{
			temp_parent->child_right = new_node;
		}
		cout<<"Value: "<<new_node->value<<"  Parent value: "<<(new_node->parent)->value<<"\n\n";
	}
}


/*
This is a recursive function to traverse 
the binary tree INORDER
*/

void main_class::recursive_traverse(Node *current)
{
	if(current->child_left != NULL)
	{
		current = current->child_left;
		//cout<<"Going left to: "<<current->value;
		recursive_traverse(current);
		current = current->parent;
	}

	cout<<current->value<<" ";
	
	/* This section is for making of the Circular Linked list*/
	
	if(previous_node == NULL)
	{
		/* This is the head*/ 
		previous_node = current; 
		root = current; 
		//root->child_left = NULL;
		//previous_node->child_left = NULL;
	}
	else
	{
		//previous_node->child_right = current; // Logical error here. The tree structure is being changed 
		                                        //before the tree can be traversed!
		current->child_left = previous_node;  
		previous_node = current;
	}
	/* Section for making of the Linked List ends here */

	if(current->child_right !=NULL)
	{
		current = current->child_right;
		//cout<<"Going right to: "<<current->value;
		recursive_traverse(current);
	}

	return;
}

{
	new Node(7);	new Node(4);	new Node(3);	new Node(5);
	new Node(15);	new Node(12);	new Node(10);	

	recursive_traverse(root);

	Node *an_iterator = previous_node;

	/*The following part connects the root node 
	to the last node making the queue circular
	*/
	root->child_left = previous_node;
	previous_node->child_right = root;

	/* The following prints the Linked list
	to check if it is indeed the list that
	was intended. It also makes it a double 
	linked list form a single linked list while doing so.
	It was not possible to make a double linked list
	to begin with because it was creating a logical
	error as indicated a few lines of code below.
	Hence, iterating from right to left.
	*/

	cout<<"\n\nThe Linked list: ";
	while (an_iterator != root)
	{
		cout<<an_iterator->value<<" ";
		an_iterator->child_left->child_right = an_iterator;
		an_iterator = an_iterator->child_left;
	}

	/*
	This extra print statement has to be put 
	outside to print the root node's valuel
	*/
	cout<<an_iterator->value<<" ";
	
	cout<<"\n\n";

}

Isnt the problem statement to convert the existing bst to a ll and not creating a new one!!!

This is the well working code for this problem..:)

#include<iostream>
using namespace std;
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#define MAX 1000
#define max(a,b) (a)>=(b)?(a):(b)
#define REP(i,n) for(i=0;i<n;i++)
#define FOR(i,a,b) for(i=a;i<b;i++)
#include<stdlib.h>
/*** structure of the tree node ****/
struct node
{
int data;
node *small;
node *large;
};
/* fun to insert element in the binary search tree */
void insert(node **root,int val)
{
node *tmp;
if(*root==NULL)
{
tmp=(node*)malloc(sizeof(node));
tmp->data=val;
tmp->small=NULL;
tmp->large=NULL;
*root=tmp;
}
else
{
if(val<(*root)->data)
insert(&((*root)->small),val);
else
insert(&((*root)->large),val);
}
}
/* this function joins two given nodes */
void join(node **a,node **b)
{
(*a)->large=(*b);
(*b)->small=(*a);
}

/* this function appends second list behind first list */
node *append(node *head1,node *head2)
{
if(head1==NULL)
return head2;
if(head2==NULL)
return head1;
node *alast,*blast;
alast=head1->small;
blast=head2->small;

join(&alast,&head2);
join(&blast,&head1);
return head1;
}

/**** most important function ,uses recursion to convert bst to circular ll ***/

node* treetolist(node *root)
{
if(root==NULL)
return NULL;
node *alist,*blist;
alist=treetolist(root->small);
blist=treetolist(root->large);

root->small=root;
root->large=root;

alist=append(alist,root);
alist=append(alist,blist);

return alist;
}
/* funtion to display bst */
void display(node *root)
{
if(root!=NULL)
{
display(root->small);
cout<<root->data<<"\t";
display(root->large);

}
}
/* function to display ll */
void displayl(node *head)
{
for(int i=1;i<=5;i++)
{
cout<<head->data<<"\t";
head=head->large;
}
}
int main()
{
node *root=NULL;
node *head;
/* test values */
insert(&root,10);insert(&root,4);insert(&root,8);insert(&root,15);insert(&root,9);
display(root);
cout<<endl;
head=treetolist(root);
displayl(head);
return 0;
}

I personally feel that we should not be pasting whole bunch of code.Motivation of this forum should be to give readers direction to think n implement themselves.

One way of doing this is with a recursive function that returns the head of the list, and also keeps track of the tail. We visit the right subtree first, then the current node (and link the tail to it), then the left sub-tree:

template<typename T>
struct ListNode
{
    T value;
    ListNode* next;
    explicit ListNode(T v) : value(v), next(NULL) { }
};
template<typename T>
struct TreeNode
{
    T value;
    TreeNode* left;
    TreeNode* right;
};


template<typename T>
ListNode<T>* to_list(TreeNode<T>* tree, ListNode<T>*& tail)
{
    ListNode<T>* list = NULL;
    if (tree)
    {
        list = to_list(tree->right, tail);
        ListNode<T>* node = new ListNode<T>(tree->value);
        if (!list)
        {
            list = node;
        }
        if (tail)
        {
            tail->next = node;
        }
        tail = node;
        node->next = to_list(tree->left, tail);
    }
    return list;
}

what nagendra.kumar suggested is right.
this way list would be sorted in increasing order and each element would be pointing
to the smallest as per the question.And there is no need to traverse right subtree first.

i m using double linked list....

node *p=NULL; 
node* Cirq(node *t)//we have call with root node....
 {
     
      if(t->left !=NULL)
      { 
          p=tree(t->left);
          p->right=t;
          t->left=p;
      }
      else if(t->right !=NULL)
      {
          p=tree(t->right);
          t->right=p;
          return p;
      }
      else
      { 
          return t;
      }
 }

@ drunkcoder : you're way too much drunk to put any no-nonsense statement !

not a single code is working. everyone is pasting just a bunch of crap !
can someone put some working code out here ?

Inorder traversal would print the numbers in icreasing order for Binary search tree.

inorder(Node *root)
{
if(root)
{
inorder(root->left);
//printf("%d", root->value); Instead of print to just assign the next poiter to end //of the list. I guess that shoudn;t be hard to figure how to assign the next link ;-)
inorder(root->right);
}
}

// Routine to convert tree into doubly list
// after conversion "right" points to "next" node and "left" points to "prev" node

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 like this,

head = toList(root, 0);

this routine returns head of the list. head and tail is not linked that can be done easily.

typedef node * NodePtr;

node *CreateListFromTree(node *root)
{
        NodePtr start = NULL, tail = NULL;
        CreateListFromTreeCore(root,&start,&tail);
        return start;
}

/* Assume right for tree will act as next for Linked List */
void CreateListFromTreeCore(node *root, NodePtr *start, NodePtr *tail)
{
        CreateListFromTreeCore(root->left,start,tail);
        node *temp = root->right;
        root->left = NULL;
        if (*start == NULL)
                *start = *tail = root;
        else
        {
                (*tail)->right = root;
                *tail = root;
        }
        *tail->right = *start;
        CreateListFromTreeCore(temp,start,tail);
}

Question is convert BST to LL but not create another list and copy values.
here is working solution.

btnode* formListFromBT(btnode* root, btnode* cur, btnode** head) {
if(!root) return cur;

cur = formListFromBT(root->left, cur, head);
if(*head == NULL) {
*head = cur = root;
}
cur->left = root; cur = cur->left;

cur = formListFromBT(root->right, cur, head);
}

// call the above function using...
btnode *listhead = NULL;
tail = formListFromBT(head, NULL, &listhead);
tail->left = listhead;

//call will be
// Element *start = null;
// Element *tail = BuildCircularLL(root, &start);
// tail->left = start;

Element *BuildCircularLL(Element *head, Element **start)
{
	Element *begin = *start;
	Element *node = head;
	Element *prev = null;
	Element *after = null;
	if(node == null)
	{
		return null;
	}
	prev = BuildCircularLL(&node->left, &begin); 
	if(prev != null)
	{
		if(begin == null)
		{
			begin = prev;
		}	
		prev->left = node;
	}
	after = BuildCircularLL(&node->right, &begin);
	if(after != null)
	{
		node->left = after;
		node->right = null;
		return after;
	}
	else
	{
		return node;
	}

}

static LinkedListNode getCircleList (BinaryTreeNode root, LinkedListNode[] headtail){
if(root == null) return null;

getCircleList(root.getLeft(), headtail);

if(headtail[0] == null){
headtail[0] = new LinkedListNode(root.getData());
}else if(headtail[1] == null){
headtail[1] = new LinkedListNode(root.getData());
headtail[0].setNext(headtail[1]);
headtail[1].setNext(headtail[0]);
}else{
LinkedListNode tmp = new LinkedListNode(root.getData());
headtail[1].setNext(tmp);
headtail[1] = tmp;
headtail[1].setNext(headtail[0]);
}

getCircleList(root.getRight(),headtail);

return headtail[0];
}

public static void main(String[] args){


BinaryTreeNode root2 = new BinaryTreeNode(5);
root2.setLeft(new BinaryTreeNode(3));
root2.setRight(new BinaryTreeNode(7));
root2.getLeft().setLeft(new BinaryTreeNode(2));
root2.getLeft().setRight(new BinaryTreeNode(4));

LinkedListNode head = getCircleList(root2, new LinkedListNode[]{null,null});

head.print();
}

struct node* T2L(n)
	if(n == NULL)
		return NULL
	l = T2L(n->l)
	r = n->right
	r->left = n
	n->left = l
	return r

struct node* T2L(n)
	if(n == NULL)
		return NULL
	l = T2L(n->left)
	r = n->right
	r->left = n
	n->left = l
	return r

Algorithm :
The problem can be solved recursively.
1. Convert the left subtree into a doubly linked list
2. Convert the right subtree into doubly linked list
3. root.left= the rightmost node of the doubly linked list of the left subtree.
4. root.right=the leftmost node of the doubly linked list of the right subtree.
5 return root.
At the end of recursion, from the main routine, traverse to the leftmost node
which gives the headnode of the doubly linked list.
You can find a perfectly working Java implementation in the below link.
cslabprograms.blogspot.com/2011/02/convert-binary-tree-to-doubly-linked.html

<pre lang="" line="1" title="CodeMonkey46488" class="run-this">node *traverseInOrder(node *root, node *prev) {
if(root->left) prev = traverseInOrder(root->left, prev);
prev->right = root;
root->left = prev;
if(root->right) return traverseInOrder(root->right, root);
else return root;
}

node *treeToList(node *root) {
node *head = new node(0), *temp = traverseInOrder(root, head);
head = head->right;
head->left = temp;
temp->right = head;
node *temp1 = temp;
int _value = 0;
do {
if(temp1->data <= _value) {
printf("new value:%d\n",temp1->data);
_value = temp1->data;
head = temp1;
}
temp1 = temp1->right;
}while(temp1 != temp);
return head;
}</pre>

1. Do inorder traversal. instead of printing, add the node to the linked list.
2. reverse the linked list
3. make the tail of the linked list point to the head to get the circular linked list

1. Do inorder traversal. instead of printing, add the node to the linked list.
2. reverse the linked list
3. make the tail of the linked list point to the head to get the circular linked list

preorder traversal

I think it should be implemted by using Breadth-first traversal.