[algogeeks] Re: Zig Zag tree traversal

[Navneet]

Liao, your solution will generate the required manner. However, can
you try to do the same by using some bool value and a single stack/
queue? Let bool value decide whether you want to insert right to left
or left to right. Haven't tried myself but think that should work.

Karthik, never did i mention it's a complete binary tree. Maybe, in
your interview, interviewer mentioned it's a complete binary tree.

On Aug 28, 7:00 pm, KARTHIKEYAN V.B. algo...@gmail.com wrote:
 use one queue

 Enqueue all the nodes in normal level order traversal in the queue

 as 1 2 3 4 5 6 7

 Each level contains 2 to the power n nodes in the queue.

 have two pointers ptr1 and ptr2

 point ptr1 to the start node of 2 power n nodes range and ptr2 to the last
 node of this range.

 For odd levels print nodes from ptr1 to ptr2

 For even levels print nodes from ptr2 to ptr1

 Keep count for odd and even levels so that it may be easy

 This was my question in Microsoft Interview for Internship in the 2nd round.

 But I too gave the solution using two stacks but the interviewer told me
 this approach.

 Regards,
 Karthik.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Zig Zag tree traversal

[siddharam suresh]

if its only printing the values then



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;
}

void get_width(node temp, int level,int direction)
{
 if(temp==NULL) return 0;
 if(level==1) {printf(%d,temp-data);}
 if(level1)
  {
  if(direction)
 {
 get_width(temp-L,level-1,direction);
 get_width(temp-R,level-1,direction);
 }
 else
 {
 get_width(temp-R,level-1,direction);
get_width(temp-L,level-1,direction);

 }


}
}
int max_width()
{
 int height,i;
 int width=0,maxwidth=0,level;
 height=get_height(root);
 for(level=0,i=0;i=height;i++,level++)
 {

 width=get_width(root,level,i%2);

}
 return(maxwidth);
}

Thank you,
Sid.



On Sun, Aug 28, 2011 at 10:58 PM, Kunal Patil kp101...@gmail.com wrote:

 @ Kartikeyan:
 If you use normal queue implementation how you are going to print
 reverse???
 (From ptr2 to ptr1)...If you are implementing queue in an array, then your
 solution can be feasible..
 If not in array, you must modify your queue DS to include pointers to
 previous elements.
 Or you can do this by emptying queue into stack n then printing nodes...
 Am I getting it correct? Or is there anything I am missing?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Zig Zag tree traversal

[siddharam suresh]

bit alteration to the max width problem, thats it nothing else.
Thank you,
Sid.



On Sun, Aug 28, 2011 at 11:07 PM, siddharam suresh
siddharam@gmail.comwrote:

 if its only printing the values then



 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;
 }

 void get_width(node temp, int level,int direction)
 {
  if(temp==NULL) return 0;
  if(level==1) {printf(%d,temp-data);}
  if(level1)
   {
   if(direction)
  {
  get_width(temp-L,level-1,direction);
  get_width(temp-R,level-1,direction);
  }
  else
  {
  get_width(temp-R,level-1,direction);
 get_width(temp-L,level-1,direction);

  }


 }
 }
 int max_width()
 {
  int height,i;
  int width=0,maxwidth=0,level;
  height=get_height(root);
  for(level=0,i=0;i=height;i++,level++)
  {

  width=get_width(root,level,i%2);

 }
  return(maxwidth);
 }

 Thank you,
 Sid.



 On Sun, Aug 28, 2011 at 10:58 PM, Kunal Patil kp101...@gmail.com wrote:

 @ Kartikeyan:
 If you use normal queue implementation how you are going to print
 reverse???
 (From ptr2 to ptr1)...If you are implementing queue in an array, then your
 solution can be feasible..
 If not in array, you must modify your queue DS to include pointers to
 previous elements.
 Or you can do this by emptying queue into stack n then printing nodes...
 Am I getting it correct? Or is there anything I am missing?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.