Re: [algogeeks] Zig Zag tree traversal
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] Zig Zag tree traversal
You can use two stacks(A, B) when traversal. Use A as the stack when traveling the odd levels. B as the even levels. A.push(1); A.pop(); //1 //push the son of the node 1, from left to right; B.push(2); B.push(3); B.pop(); // 3 //push the son of the node 3, from right to left A.push(7); A.push(6); B.pop(); // 2 A.push(5); A.push(4); A.pop(); //4 A.pop(); //5 A.pop(); //6 A.pop(); //7 Just like this. On Sun, Aug 28, 2011 at 7:03 AM, Navneet Gupta wrote: > Print tree in zig zag manner > > 1 >/ \ > 23 > / \ / \ > 4 56 7 > > O/P: 1 3 2 4 5 6 7 > > > -- > Regards, > Navneet > > -- > 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. > > -- from Yuchen Liao via Gmail -- 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.
[algogeeks] Zig Zag tree traversal
Print tree in zig zag manner 1 / \ 23 / \ / \ 4 56 7 O/P: 1 3 2 4 5 6 7 -- Regards, Navneet -- 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.