CareerCup

Traverse the tree till you reach the leftmost leaf. After that go to it's parent and reverse the link. Do this until u find the root. Hence u would have converted the tree into a list with head at the leftmost leaf.

Do an inorder traversal and instead of printing start putting it in a link list.

Instead of putting it into a linked list I think the existing pointers can be rearranged to form the doubly linked list.

Using inorder traversels we convert the binary tree into linked list.

the following code works:
struct Tree
{
int i;
struct Tree* left;
struct Tree* right;
};
Tree * Convert_to_list (Tree* T)
{
Tree * T1, T2, temp;
if (T != NULL)
{
T1 = Convert_to_list(T->left)
T2 = Convert_to_list(T->right)
T->right = T2;
if (T1!= NULL)
{
temp = T1;
while (temp->right)
temp = temp->right;
temp->right = T;
return T1;
}
else
return T;
}
else
return NULL;
}

this is for generating singly linked list

Node* head = NULL;
Node* tail = NULL;
tree.ConvertToList(tree.root,&head, &tail);

void Tree::ConvertToList(TNode* root, Node** head, Node** tail)
{
if(root)
{
ConvertToList(root->left,head,tail);

Node* node = new Node();
node->data = root->data;
node->next = NULL;

if(!*tail)
{
*head = node; //store the first node in head pointer
*tail = node;
}
else
{
(*tail)->next = node;
*tail = node;
}

ConvertToList(root->right,head,tail);
}
}

Void convertTreeToList()
{
First = ConvertTreeToList(root);
}
TreeNode* ConvertTreeToList(TreeNode *treePtr)
{
If(treePtr != null)
{
listLeft = ConvertTreeToList(treePtr->Left);
listRight = ConvertTreeToList(treePtr->Right);
treePtr->Right = listRight;
treePtr->Left = NULL;
if(listLeft==NULL)
return treePtr;
temp = listLeft;
while(temp->Right!=null)
temp=temp->Right;
temp->Right = treePtr;
return listLeft;
}
Return NULL;
}

void BstToList( Node * root , node & left , node & right )
{
node l1 , l2 , r1 , r2 ;
if ( root == NULL )
return ;
BstToList(root->left , l1 , r1) ;
r1->next = root ;
BstToList( root->right , l2 , r2 ) ;
root->next = l2 ;
l = l1 ;
r = r2;
}
// end function

Can somebody post the pusedo code instead of C Code ?

A sample Pseudocode :

There will be three functions:

traverseTree(TREE tnode, LINK lnode);
main();
processNodes(TREE tnode, LINK lnode);

main()
{
allocate link_node;

declare link_head AS link_node;
declare tree_node AS tree_root;

traverseTree(tree_node,link_node);

link_node = null;

display(link_head);
}

traverseTree( TREE tnode, LINK lnode)
{
if (tnode == null)

{
return;
}

else
{

traverseTree (tnode->left, lnode)
processNodes (tnode,lnode)
traverseTree (tnode->right, lnode)

}

}

processNodes( TREE tn, LINK ln)
{
ln->value = tn->value;
allocate a new link node newLinkNode;
ln->next = newLinkNode;
ln = ln->next;
}

That's it. The code assumes that every tree node has a left and right pointer and the link list is singly listed. If it is to be made a doubly listed one, then altering the processNodes function alone does the trick.

display is a generic function that iterates through the link list and displays its value.

Xons pseudo looks fine - but it has a small mistake I guess. The "LINK ln" should be global because the purpose of ln=ln->next is lost if LINK ln is local to the function processNodes(). So instead of passing lnode in traverseTree() and processNode() declare the list globally so that the statement ln=ln->next purpose is not lost. Otherwise what happens is - you always modify the ln->value you and you come out of processNodes and ln goes out of scope and is no longer visible to the next function traverseTree(tnode->right, lnode) ;

so put list in global space.
change traverseTree(tnode->right, lnode);
to traverseTree(tnode->right); and the same for left;

and
change processNodes( TREE tn, LINK ln);
to processNodes( TREE tn);

allocate link_node; //global variable

main()
{
declare link_head AS link_node;
declare tree_node AS tree_root;
traverseTree(tree_node,link_node);
link_node = null;
display(link_head);
}

traverseTree( TREE tnode)
{
if (tnode == null)
{
return;
}
else
{
traverseTree (tnode->left)
processNodes (tnode)
traverseTree (tnode->right)
}
}

processNodes( TREE tn)
{
link_node->value = tn->value;
allocate a new link_node newLinkNode;
link_node->next = newLinkNode;
link_node = link_node->next;
}

typedef struct n
{
int val;
struct n *left, *right;

}
n_t;

n_t *conv( n_t *t)
{
n_t *l = NULL, *r = NULL;
cl (t, &l, &r);
return l;
}

void cl (n_t *t, n_t **l, n_t **r)
{
n_t *tl = NULL, *tr = NULL;
if (t->left == NULL && t->right == NULL)
{
t->left = NULL;
t->right = NULL;
*l = t;
*r = t;
return;
}

if (t->left != NULL)
{
cl (t->left, l, &tr);
}
if (t->right != NULL)
{
cl (t->right, &tl, r);
}
t->left = tr;
t->right = tl;
if (tl == NULL)
*r = t;
else
tl->left = t;
if (tr == NULL)
*l = t;
else
tr->right = t;


}

will the above work ?

Why can't we just use a bfs/dfs? and just put in the nodes in a list/stack as we do to do a bfs/dfs? how is using inorder/preorder traversal better than it?

/*right pointer of each treeNode works as the next pointer for a single linked list*/
Convert(TreeNode root) returns LinkedList Start Node
begin

/*Trivial case when there is no tree/1 node tree*/
if(root IS NULL) OR ((root.right IS NULL) AND (root.left IS NULL))
begin
start <- root
end

else
begin
/*convert left subtree to a list*/
if(root.left IS NOT NULL)
begin
start <- Convert(root.left)
/*find the last node of left list*/
leftEnd <- start
while(leftEnd.right IS NOT NULL)
begin
leftEnd <- leftEnd.right
end
/*append root to the left subtree list*/
leftEnd.right <- root;
end

/*convert right subtree to a list*/
if(root.right IS NOT NULL)
begin
rightStart <- Convert(root.right)
/*append right subtree list to the root*/
root.right <- rightStart
end
end

/*return the formed list left subtree list <- root <- right subtree list*/
return start
end

@jhonny...whats wrong in doing it in an INORDER traversal....and what made u think that way....i think XON's solution alongwith Sidarth's patch will do the job...is that clear???

tree *start_node, *q;
convert_list(tree *t)
{
if(!t)return;
convert_list(t->left);
q->next=t;
convert_list(t->right);
}

int main()
{
tree *root,*t;
start_list=root;
while(start_list->left) start_list=start_list->left;
q=start_list;
convert_list(root);
q->next=null;
}

ppl, u have only thought abt converting the convertin the BST into a linked list.
Wat if u want to convert it back to the same tree?

Then BFS wud be better rite?

tree itself is not a linkedlist??