CareerCup

Solution using a queue and stack. No hack. o(n2)

Convert2DLL(Queue queue,int level, list** head)
{
 Queue nextqueue;
 Stack stack;

  if (queue.empty())
     return;

 while ( !queue.emtpy() )
 {
    TNode *node= queue.pop();

    if (level%2 == 1)
    {    
        stack.push(node->left);
       stack.push(node->right);
    }
    else
    {
        nextqueue.push(node->left);
        nextqueue.push(node->right);       
    }

    *head->right=node;
     node->left=*head;   
     *head=node;
     *head->right=null;        
 }

 if ( level%2 == 1)
 {
   while ( !stack.empty)
   {
      node *temp = stack.pop();
      nextqueue.push(temp);
   }
 }

 queue = nextqueue;
 Convert2DLL(queue,level++, head);
}

public Node convertToDoubly(Node root){
	if(root ==  null)
		return null;
	LinkedList oddLevel = new LinkedList();
	LinkedList evenLevel = new LinkedList();
	Node doubly = root;
	evenLevel.add(root);
    while(!(oddLevel.size()==0&&evenLevel.size()==0)){
		while(oddLevel.size()!=0){
			Node nd = (Node)oddLevel.remove();
			System.out.println("out - " + nd.getValue());
			if(nd.getNodeA()!=null)
				evenLevel.addFirst(nd.getNodeA());
			if(nd.getNodeB()!=null)
				evenLevel.addFirst(nd.getNodeB());
			doubly.setNodeB(nd);
			nd.setNodeA(doubly);
			nd.setNodeB(null);
			doubly = nd;
		}
		while(evenLevel.size()!=0){
			Node nd = (Node)evenLevel.remove();
			System.out.println("even - " + nd.getValue());
			if(nd.getNodeB()!=null)
				oddLevel.addFirst(nd.getNodeB());
			if(nd.getNodeA()!=null)
				oddLevel.addFirst(nd.getNodeA());
			doubly.setNodeB(nd);
			nd.setNodeA(doubly);
			nd.setNodeB(null);
			doubly = nd;
	   }
	}
	return root;  
  }

Can u not use BSF algorithm with little trick

class dbList
{
public:
int item;
dbList *left;
dbList *right;

public:
dbList(int val)
{
item = val;
left = NULL;
right = NULL;
}
};

class treeNode
{

public:

int item;
treeNode *left;
treeNode *right;


public:

treeNode(int value)
{
item = value;
left = NULL;
right = NULL;
}
};

void constructBTree(treeNode& , int);
void inorderPrint(treeNode *);
void addList(int);
dbList *node = NULL;
dbList *startList = NULL;
dbList *prevList = NULL;

int _tmain(int argc, _TCHAR* argv[])
{

//construct a Binary Tree;

treeNode *root = new treeNode(100);

treeNode *strtRoot = root;
constructBTree(*strtRoot, 50);

strtRoot = root;
constructBTree(*strtRoot, 75);

strtRoot = root;
constructBTree(*strtRoot, 25);

strtRoot = root;
constructBTree(*strtRoot, 175);

//convert tree in to a doubly linked list.
//Parse through tree and add double linked list nodes.
inorderPrint(root);

for (dbList *hdr = node; hdr != NULL; hdr = hdr->left)
cout << hdr->item << " ";


return 0;
}

void addList(int val)
{
if (node != NULL)
{
if (node == startList)
{
node->right = new dbList(val);
prevList = node;
node = node->right;
node->left = prevList;
}
else
{
prevList = node;
node->right = new dbList(val);
node = node->right;
node->left = prevList;
}
}
else
{
node = new dbList(val);
startList = node;
}
}
void constructBTree(treeNode& root, int val)
{
/*if (root == NULL)
return;*/

if (root.item >= val && root.left == NULL)
root.left = new treeNode(val);
else if (root.item >= val)
constructBTree(*(root.left), val);
else if (root.item < val && root.right == NULL)
root.right = new treeNode(val);
else if (root.item < val)
constructBTree(*(root.left), val);
}

void inorderPrint( treeNode *root )
{
// Print all the items in the tree to which root points.
// The items in the left subtree are printed first, followed
// by the item in the root node, followed by the items in
// the right subtree.
if ( root != NULL )
{ // (Otherwise, there's nothing to print.)
inorderPrint( root->left ); // Print items in left subtree.
//cout << root->item << " "; // Print the root item. // 25, 50, 75, 100, 175
addList(root->item);
inorderPrint( root->right ); // Print items in right subtree.
}
} // end inorderPrint()

#include<stack>
#include<algorithm>
using namespace std;

//node->left becomes node->next, node->right becomes node->previous
Node* convertToDLL(Node* root)
{
if(root == NULL) return NULL;
stack<Node*> s1, s2;
s1.push(root);
Node* pre = root;
int level = 0;
while(!s1.empty())
{
Node* temp = s1.top();
s1.pop();
if(level%2){
if(temp->left) s2.push(temp->left);
if(temp->right) s2.push(temp->right);
}
else
{
if(temp->right) s2.push(temp->right);
if(temp->left) s2.push(temp->left);
}
pre->left = temp;
temp->right = pre;
pre = temp;
if(s1.empty())
{
swap(s1,s2);
level++;
}
}
pre->left = NULL;
root->right = NULL;
return root;
}

void btoll(node root)
{
node temp;
node even_stack_top;
node odd_stack_top;
even_push(root);
while(!odd_underflow() && !even_underflow())
{

while(!even_underflow())
{
temp=even_pop();
odd_push(temp->left);
odd_push(temp->right);
if(even_underflow())
{
odd_stack_top = odd_pop();
temp->right=odd_stack_top;
odd_push(odd_stack_top);
}
}
while(!odd_underflow())
{
temp=odd_pop();
even_push(temp->right);
even_push(temp->left);
if(odd_underflow())
{
even_stack_top=even_pop();
temp->right=even_stack_top;
even_push(even_stack_top);
}
}
}

}




some part of this not working.
algo as follows.
1)create 2 stacks evenstack,oddstack
2)push root to evenstack
3)while both stacks are not empty repeat
3.1)while even stack is empty repeat
3.1.1)pop temp from even stack
3.1.2)push (temp->left) to odd stack
3.1.3)push (temp->right) to odd stack
3.1.4) if evenstack is empty
3.1.4.1) then temp->right = oddstack[odd_tos]
3.2)while odd stack is empty repeat
3.2.1)pop temp from odd stack
3.2.2)push (temp->right) to even stack
3.2.3)push (temp->left) to even stack
3.2.4) if oddstack is empty
3.2.4.1) then temp->right = evenstack[even_tos]


i feel algo is fine and above program is not working.
please tell modifications.

void btoll(node root)
{
node temp;
node even_stack_top;
node odd_stack_top;
even_push(root);
while(!odd_underflow() && !even_underflow())
{

while(!even_underflow())
{
temp=even_pop();
odd_push(temp->left);
odd_push(temp->right);
if(even_underflow())
{
odd_stack_top = odd_pop();
temp->right=odd_stack_top;
odd_push(odd_stack_top);
}
}
while(!odd_underflow())
{
temp=odd_pop();
even_push(temp->right);
even_push(temp->left);
if(odd_underflow())
{
even_stack_top=even_pop();
temp->right=even_stack_top;
even_push(even_stack_top);
}
}
}

}




some part of this not working.
algo as follows.
1)create 2 stacks evenstack,oddstack
2)push root to evenstack
3)while both stacks are not empty repeat
3.1)while even stack is empty repeat
3.1.1)pop temp from even stack
3.1.2)push (temp->left) to odd stack
3.1.3)push (temp->right) to odd stack
3.1.4) if evenstack is empty
3.1.4.1) then temp->right = oddstack[odd_tos]
3.2)while odd stack is empty repeat
3.2.1)pop temp from odd stack
3.2.2)push (temp->right) to even stack
3.2.3)push (temp->left) to even stack
3.2.4) if oddstack is empty
3.2.4.1) then temp->right = evenstack[even_tos]


i feel algo is fine and above program is not working.
please tell modifications.

i got solution but it's not in place

#include<stdio.h>
struct NODE
{
int data;
struct NODE *R;
struct NODE *L;
};
typedef struct NODE* node;
node root=NULL;
int buildTree(int item)
{
node temp1,temp2,ins;
temp2=temp1=root;
ins=(struct NODE*) malloc(sizeof(struct NODE));
ins->L=NULL;
ins->R=NULL;
ins->data=item;
if(root==NULL) {root=ins; return 0;}
while(temp1!=NULL)
{
if(temp1->data<item)
{
temp2=temp1;
temp1=temp1->R;
}
else
{
temp2=temp1;
temp1=temp1->L;
}
}
if(temp2->data<item) temp2->R=ins;
else temp2->L=ins;
return 0;
}int get_height(node temp)
{
if(temp!=NULL)
{
return(get_height(temp->L)>get_height(temp->R)?(get_height(temp->L)+1):(get_height(temp->R)+1));
}
return 0;
}

int get_width(node temp, int level,int flag)
{
if(temp==NULL) return 0;
if(level==1) {printf("%d\t",temp->data);/* we should malloc here*/ return 1;}
if(flag)
return(get_width(temp->L,level-1,flag)+get_width(temp->R,level-1,flag));
else
return(get_width(temp->R,level-1,flag)+get_width(temp->L,level-1,flag));
}
int max_width()
{
int height,i;
int width=0,maxwidth=0,level;
height=get_height(root);
printf("the height is:%d\n",height);
for(level=1;level<=height;level++)
{
width=get_width(root,level,level&1);
if(width>maxwidth) maxwidth=width;
}
return(maxwidth);
}

void inorder(node n)
{
if(n!=NULL)
{
inorder(n->L);
printf("%d\t",n->data);
inorder(n->R);
}
}
void preorder(node n)
{
if(n!=NULL)
{
printf("%d\t",n->data);
preorder(n->L);
preorder(n->R);
}
}
void postorder(node n)
{
if(n!=NULL)
{
postorder(n->L);
postorder(n->R);
printf("%d\t",n->data);
}
}

int main()
{
int i,n,num;

printf("Enter the number of element:\n");
scanf("%d",&n);
while(n--)
{
printf("Enter the element:\n");
scanf("%d",&num);
buildTree(num);
}
max_width();


}

A SIMPLE SOLUTION-USE BFS

public class Node{
	int value;
	boolean visited;
	public Node(int value){
		this.value=value;
		visited=false;
		}
public class BST{
	Node root;
	public BST(){
		Node root=null;
		}
public List returnBST(Node rootNode)
{
	Queue<Node> q=new LinkedList<Node>();
	List<Node> list=new LinkedList<Node>();
	q.add(this.rootNode);
	list.add(this.rootNode);
	rootNode.visited=true;
	while(!q.isEmpty())
	{
		Node n=(Node)q.remove();
		Node child=null;
		while((child=getUnvisitedChildNode(n))!=null)
		{
			child.visited=true;
			list.add(child)
			q.add(child);
		}
	}
	return list;
}

Let's consider that the PREV of Linked List be LEFT and the NEXT of Linked List be RIGHT

Initially, head is NULL

void rec_convert(node* root, node **head)
{
       if(!root)
               return;

       rec_convert(root->right,head);

       root->right = *head;

       if((*head))
               (*head)->left = root;

       *head = root;

       rec_convert(root->left, head);
}

create_dll(Queue *q, node *root, node *dll)
{
if(root)
create_queue(q, root);
else
return;
if(dll == NULL)
{
dll = root;
dll->left=NULL;
dll->right=NULL;
}
else
{
dll->right=root;
root->left=dll;
dll=dll->right;
root->right=NULL;
}
Node *temp = dequeue(q)
}


create_queue(Queue *q, node *n)
{
q->enqueue(n->left);
q->enqueue(n->right);
}


i think it should work.