CareerCup

Do an in-order traversal of the binary tree, at each node joining the linked list resulting from the left and right children.

just use the morris inorder traversal :)

public Node BSTtoDL(Node nd, Node lastPrintedNode){

if(nd.getLeft()!=null)
lastPrintedNode = BSTtoDL(nd.getLeft(),lastPrintedNode);

if(lastPrintedNode == null)
{
lastPrintedNode = nd;
nd.setLeft(null);
}
else
{
lastPrintedNode.setRight(nd);
nd.setLeft(lastPrintedNode);
}
if(nd.getRight()!=null)
lastPrintedNode = BSTtoDL(nd.getRight(), lastPrintedNode);

return lastPrintedNode; 
}

F(n, b)
	if(!n->r && !n->l)
		return n
	nl = F(n->l, 0)
	nr = F(n->r, 1)
	n->l = nl
	nl->r = n
	n->r = nr
	nr->l = n
	if(b)
		return nl
	else
		return nr

can we use recursion ??

#include<iostream>

using namespace std;

class TreeNode
{
public:
int info;
TreeNode* right;
TreeNode* left;
//TreeNode* parent;
TreeNode()
{
info = 0;
right = left = NULL;
}

TreeNode(int info)
{
this -> info = info;
right = left = NULL;
}
};

class ListNode
{
public:
int info;
ListNode* next;
ListNode()
{
info = 0;
next = NULL;
}

ListNode(int info)
{
this -> info = info;
next = NULL;
}
};

TreeNode* root = NULL;
ListNode* start;
ListNode* end;

void addTreeNode(TreeNode*);
void convertTreeToList(TreeNode*);
void printList(ListNode*);
int findDepth(TreeNode*);

int main()
{
start = end = new ListNode(0);
char choice = 'y';
int info;
while(choice == 'y')
{
cout<<"Enter the info of new node:\n";
cin>>info;
addTreeNode(new TreeNode(info));
cout<<"Want to add a new node to the tree?(y/n)\n";
cin>>choice;
}

cout<<"Depth of the tree is: "<<findDepth(root);

cout<<"Converting the tree into a doubly linked list....\n";

convertTreeToList(root);
printList(start->next);
cin>>choice;
return 0;
}



void addTreeNode(TreeNode* node)
{
if(!root)
{
root = node;
}
else
{
TreeNode* currRoot = root;
while(1)
{
if(node -> info >= currRoot -> info)
{
if(!currRoot -> right)
{
currRoot -> right = node;
break;
}
else
{
currRoot = currRoot -> right;
}
}
else
{
if(!currRoot -> left)
{
currRoot -> left = node;
break;
}
else
{
currRoot = currRoot -> left;
}
}
}
}
}

void convertTreeToList(TreeNode* node)
{
if(node -> left != NULL)
{
convertTreeToList(node -> left);
}

end ->next = new ListNode(node -> info);
end = end -> next;
end -> next = start;



if(node -> right != NULL)
{
convertTreeToList(node -> right);
}

}


void printList(ListNode* start)
{
while(start != ::start)
{
cout<<start->info<<" -> ";
start = start -> next;
}
cout<<"x";
}

int findDepth(TreeNode* node)
{
if(!node)
{
return 0;
}
else
{
return (max(findDepth(node -> left), findDepth(node -> right)) + 1);
}
}

follow this link.............

programmingwar.blogspot.com/2011_10_01_archive.html

Converting to singly linked list (can easily be modified to dll).
-1. r = root
0. Until node r has no children
1. Keep rotating right until there is no left child or r
2. set r = r->right;
3. go to step 0

TNode* Tree::rr(TNode* r)
{
TNode* A = r;
TNode* B = r->left;
TNode* Br = B->right;

B->right = A;
A->left = Br;

return B;
}

void Tree::convertToLL()
{
TNode* r = root;
TNode* p = NULL; // parent

while ( r->left != NULL || r->right != NULL )
{
while ( r->left != NULL )
{
r = rr(r);
if ( p != NULL )
p->right = r;
else
root = r;
}
p = r;
r = r->right;
}
}