Amazon Interview Question
Software Engineer / Developerspublic 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;
}
Well, I guess this one is more of a implementation question then of algo or logic. But still let me try.
Keep 2 lists evenlist(this will contain the nodes at even level considering root node at zero level.) and similarly the oddList.
When you start traversing the evenList populate the oddlist with the children nodes in evenList and remove the elements from evenlist simultaneously, and similarly do same while traversing the oddlist. All you have to do is be CAREFUL ABOUT THE ORDER while populating and accessing the lists. at the end when you have no more elemnts in any of the lists, you break out of the loop.
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.
Solution using a queue and stack. No hack. o(n2)
- hari@hbiz.in August 14, 2012