Printing a Binary Tree in Zig Zag Level-Order

Given a binary tree, print out the tree in zig zag level order (ie, from left to right, then right to left for the next level and alternate between). Output a newline after the end of each level.

     3
   /  \
  9   20    
     /  \
    15    7

For example, the zig zag level order output of the tree above is:

3 
20 9
15 7

This question is a variation of the question Printing a Binary Tree in Level Order.

Hint:
Queue is not helpful here. You might want to consider using Stack instead.

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level’s order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node’s value. Whenever the current level’s order is from left->right, you push the node’s left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level’s order is from right->left, you would push the node’s right child first, then its left child. Finally, don’t forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

VN:F [1.9.22_1171]
Rating: 4.7/5 (49 votes cast)
Printing a Binary Tree in Zig Zag Level-Order, 4.7 out of 5 based on 49 ratings

106 thoughts on “Printing a Binary Tree in Zig Zag Level-Order

        1. Ralph

          this is caused by cultural difference. if you don’t speak chinese well you might also make such mistakes posting in chinese forums. and when someone made such a mistake we don’t call him an idiot in public forums. we understand and just smile 🙂

          VN:F [1.9.22_1171]
          +16
  1. 1337c0d3r

    Using two stacks is correct and I have verified it in the program. However, I'm interested in knowing alternative solutions.

    Could you please give an example on how would you use one stack and one queue to print the zig-zag order 0, 1, 2, …, 14?

    ___ 0___
    / \
    1 2
    / \ / \
    6 5 4 3
    / \ / \ / \ / \
    7 8 9 10 11 12 13 14

    VA:F [1.9.22_1171]
    +1
    1. Algoseekar

      hi ihas1337

      Everything is fine Except That How are you Swapping The Two Stack,,I have Never Seens Swapping Two Stack,, I will really thanks & appreciate if you can provide the code for swapping the two stack i means stack value is swapped but order remains same. ..try to provide the code for that ASAP & u see this comment

      also how you handle the case when one stack become empty & u swapping values with null ..plz explain

      you can explain me for the whose in-order is given by 1234567 & o/p is 1324567..??

      Waiting for your solution

      Thanks
      Algoseekar

      VA:F [1.9.22_1171]
      -1
    2. Aj

      void zigzag()
      {
      nodeptr p=root;
      push1(p);
      int flag=1;
      while(flag)
      {
      if(top1)
      {
      while(top1!=NULL)
      {
      p=top1->d;
      cout<<endl<data;
      pop1();
      if(p->left)
      push2(p->left);
      if(p->right)
      push2(p->right);
      }
      }
      if(top2)
      {
      while(top2!=NULL)
      {
      p=top2->d;
      cout<<endl<data;
      pop2();
      if(p->left)
      push1(p->left);
      if(p->right)
      push1(p->right);
      }
      }
      if(top1==NULL && top2==NULL)
      flag=0;
      }
      }
      push1 and pop1 for stack1 and push2 and pop2 for stack2…….nodeptr is defined as::typedef node *nodeptr:: here node was used for tree…..i think its easier to understand

      VN:F [1.9.22_1171]
      0
      1. Aj

        Instead of swapping stacks…..idea is insert root in stack1…now till it gets emptied(for first time root is popped) by pop operations push its left then right child into stack2……now till stack2 two gets emptied by pop operations push its right then left child into stack1
        ……….and so on till all nodes are pushed and popped then set flag to zero to terminate program

        VN:F [1.9.22_1171]
        0
        1. Soumojit Ghosh

          Swapping is smarter. Already your current stack is empty. So instead of popping all elements from your next and pushing them into the current, swap the pointers of your current and next stacks.

          VA:F [1.9.22_1171]
          0
    3. Soumojit Ghosh

      Yes, a queue can be used. But there is no benefit in that. In this piece of code, since a stack is being used and elements are being removed from the top, in case of queue the elements will be removed from the bottom. So the ordering would be exactly inverse. What that means is, now for a level if you are adding the left child of the current node first, you need to add the right child first.

      For ease of use, two stacks are being used and are being swapped once the current becomes empty. You can also use a deque, and alternatively remove from the right for one level and remove from the left in another. But again, no great benefit.

      VA:F [1.9.22_1171]
      0
  2. Zhibin

    My understanding is
    1)this (leftToRight) used for the switch left/right.
    2)one stack and one queue used for making the sequence of the stack opposite in the queue.
    (this is what the swap function does.)
    Otherwise, the output will be 5,6,3,4.
    —————
    If you have already verified it in the program, then probablly it really depends on how you implemented your swap() function.

    VA:F [1.9.22_1171]
    -2
  3. 1337c0d3r

    The swap function just swap the currentStack with the nextStack. Probably not very efficient, but could be changed easily to swap the pointers to the stack instead of the stack itself.

    VA:F [1.9.22_1171]
    +1
  4. Anonymous

    How about using only one stack?
    void printLevelOrderZigZag(BinaryTree *root) {
    if(!root) return;
    stack S;
    bool leftToRight = true;
    S.push(root);
    int nodesInCurrentLevel = 1;
    int nodesInNextLevel;
    while (!S.empty()) {
    nodesInNextLevel = 0;
    for(int i=0; idata << " ";
    if(leftToRight)
    {
    if(currNode->left)
    {
    S.push(currNode->left);
    ++nodesInNextLevel;
    }
    if(currNode->right)
    {
    S.push(currNode->right);
    ++nodesInNextLevel;
    }
    }
    else
    {
    if(currNode->right)
    {
    S.push(currNode->right);
    ++nodesInNextLevel;
    }
    if(currNode->left)
    {
    S.push(currNode->left);
    ++nodesInNextLevel;
    }
    }
    }
    cout << endl;
    nodesInCurrentLevel = nodesInNextLevel;
    leftToRight = !leftToRight;
    }
    }

    VA:F [1.9.22_1171]
    0
    1. Sean

      FYI, this approach doesn’t work. Surprised that no one mentioned this. If you use only one stack, Children nodes will get pushed on top of the stack before all parent nodes get popped and printed.

      VA:F [1.9.22_1171]
      0
  5. Anonymous

    I think a double-ended queue can work too. At first, the deque works as a queue (print nodes from left to right), then at the second level, it works as a stack (print nodes from right to left). then it just alternates for the rest levels.

    In essence, this is same with your solution.

    VA:F [1.9.22_1171]
    +1
  6. wgpshashank

    Here is the Recursive Solution let me Know if you Found Any problem in this ..??

    #include
    #include
    #define bool int

    /* A binary tree node has data, pointer to left child
    and a pointer to right child */
    struct node
    {
    int data;
    struct node* left;
    struct node* right;
    };

    /*Function protoypes*/
    void printGivenLevel(struct node* root, int level, int ltr);
    int height(struct node* node);
    struct node* newNode(int data);

    /* Function to print spiral traversal of a tree*/
    void printLevelOrder(struct node* root)
    {
    int h = height(root);
    int i;

    /*ltr -> Left to Right. If this variable is set,
    then the given level is traverseed from left to right. */
    bool ltr = 0;
    for(i=1; idata);
    else if (level > 1)
    {
    if(ltr)
    {
    printGivenLevel(root->left, level-1, ltr);
    printGivenLevel(root->right, level-1, ltr);
    }
    else
    {
    printGivenLevel(root->right, level-1, ltr);
    printGivenLevel(root->left, level-1, ltr);
    }
    }
    }

    /* Compute the “height” of a tree — the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
    int height(struct node* node)
    {
    if (node==NULL)
    return 0;
    else
    {
    /* compute the height of each subtree */
    int lheight = height(node->left);
    int rheight = height(node->right);

    /* use the larger one */
    if (lheight > rheight)
    return(lheight+1);
    else return(rheight+1);
    }
    }

    /* Helper function that allocates a new node with the
    given data and NULL left and right pointers. */
    struct node* newNode(int data)
    {
    struct node* node = (struct node*)
    malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
    }

    /* Driver program to test above functions*/
    int main()
    {
    struct node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(7);
    root->left->right = newNode(6);
    root->right->left = newNode(5);
    root->right->right = newNode(4);
    printf(“Level Order traversal of binary tree is \n”);
    printLevelOrder(root);

    getchar();
    return 0;
    }

    VA:F [1.9.22_1171]
    0
  7. Algoseekar

    hi ihas1337 code,,,Everything is fine Except That How are you Swapping The Two Stack,,I have Never Seens Swaping Two Stack,, I will really thanks & appreciate if you can provide the code for swaping the two stack i means stack value is swapped but order remains same. ..try to provide the code for that ASAP & u see this comment

    also how you handle the case when one stack become empty & u swapping values with null ..plz explain

    you can explain me for the whose in-order is given by 1234567 & o/p is 1324567..??

    Waiting for your solution

    Thanks
    Algoseekar

    VA:F [1.9.22_1171]
    0
  8. Algoseekar

    hi ihas1337 code,,,Everything is fine Except That How are you Swapping The Two Stack,,I have Never Seens Swaping Two Stack,, I will really thanks & appreciate if you can provide the code for swaping the two stack i means stack value is swapped but order remains same. ..try to provide the code for that ASAP & u see this comment

    also how you handle the case when one stack become empty & u swapping values with null ..plz explain

    you can explain me for the whose in-order is given by 1234567 & o/p is 1324567..??

    Waiting for your solution

    Thanks
    Algoseekar

    VA:F [1.9.22_1171]
    0
    1. codingC

      If temporary storage is allowed to use, then you dump stack1 into the temp stack, and then dump stack2 into the temp stack. Of course, you need to count how many elements in stack1 and stack2. Then you remove elements from stack2 in the temp stack and push them into stack1, and remove rest and push them into stack2. This is not efficient, but at least works.

      VA:F [1.9.22_1171]
      0
      1. Soumojit Ghosh

        Dude the stacks are being swapped when the current becomes empty. So swapping them is smarter than popping all elements from one and pushing them into the other.

        VA:F [1.9.22_1171]
        0
    2. Soumojit Ghosh

      You don’t need code. Just swap the pointers using a temporary pointer.
      It’s a two line code.
      swap(current,next){
      temp=current
      current=next
      next=temp
      }

      VA:F [1.9.22_1171]
      0
  9. Sonal

    Can we use deque instead of stacks… where depending on th level number we can either use push_front() or push_back() function…??

    VA:F [1.9.22_1171]
    0
  10. reader

    @1337c0d3r:
    It is possible to use a stack and a queue.
    You just pop all the elements of the stack to the queue.
    And then use the queue. I.e. print the elements and depending on the order (left to right or right to left) you push the current queue’s element left or right child to the queue first.
    But the code is not clear and I don’t think the complexity is very good. Your solution is much better

    VA:F [1.9.22_1171]
    0
  11. peng

    A solution without extra space (the two stacks) is to write a helper function which prints a specific level of tree in a pre-defined order:

    if order is true, left to right, else right to left

    void printLevel(Node* n, int level, bool order){

    if(n){
    if(level==1) cout<data<left, level-1, order);
    printLevel(n->right, level-1, order);
    }
    else{
    printLevel(n->right,level-1,order);
    printLevel(n->left,level-1,order);
    }
    }
    }

    VN:F [1.9.22_1171]
    0
    1. peng

      Format issue in the previous post, here it is

      void printLevel(Node* n, int level, bool order){

      if(n){
      if(level==1) cout<data<left, level-1, order);
      printLevel(n->right, level-1, order);
      }
      else{
      printLevel(n->right,level-1,order);
      printLevel(n->left,level-1,order);
      }
      }
      }

      VN:F [1.9.22_1171]
      0
  12. peng

    Hmm, weird, the format is wrong again, anyway it looks like this

    void printLevel(Node* n, int level, bool order){

    if(n){
    if(level==1) “print the data here”
    if(order){
    printLevel(n->left,level-1,order);
    printLevel(n->right, level-1, order);
    }
    else{
    printLevel(n->right,level-1,order);
    printLevel(n->left,level-1,order);
    }
    }
    }

    VN:F [1.9.22_1171]
    0
  13. Chirag

    Instead of swapping the two stacks why dont we just use the two stacks to print in different order alternately like this :

    void printLevelOrderZigZag(Node *root)
    {
    stack s1,s2;
    s1.push(root);
    Node *temp;
    while(!s1.empty() || !s2.empty())
    {
    if(!s1.empty())
    {
    while(!s1.empty())
    {
    temp = s1.top();
    cout<data <left)
    s2.push(temp->left);
    if(temp->right)
    s2.push(temp->right);
    }
    }
    else if(!s2.empty())
    {
    while(!s2.empty())
    {
    temp = s2.top();
    cout<data <right)
    s1.push(temp->right);
    if(temp->left)
    s1.push(temp->left);
    }
    }
    cout<<endl;
    }
    }

    VA:F [1.9.22_1171]
    0
  14. Chao Chen

    void printTreezigzag(BNode *root){
    stack bt_stack;
    queue bt_queue;
    bool even = true;
    BNode *curr = root;
    bt_queue.push(curr);
    int curlevel = 1;
    while(!bt_stack.empty() || !bt_queue.empty()){
    curr = bt_queue.front();
    bt_queue.pop();
    curlevel–;
    cout<val<left){
    bt_stack.push(curr->left);
    }
    }
    if(curr->right){
    bt_stack.push(curr->right);
    }
    if(!even){
    if(curr->left){
    bt_stack.push(curr->left);
    }
    }
    if(curlevel == 0){
    cout<<endl;
    while(!bt_stack.empty()){
    bt_queue.push(bt_stack.top());
    bt_stack.pop();
    }
    curlevel = bt_queue.size();
    even = !even;
    }
    }
    }

    I used one stack and one queue.

    Actually I believed that one deque can work as well.

    VA:F [1.9.22_1171]
    0
  15. Shundan Xiao

    The Deque java version. Used only one Deque, verified by OJ.

    public ArrayList<ArrayList> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    Deque dq = new LinkedList();
    boolean leftToRight = true;
    int current=0, next=0;
    if(root!=null){
    dq.offerLast(root);
    current++;
    }
    ArrayList list = new ArrayList();
    while(!dq.isEmpty()){
    TreeNode temp;
    if(leftToRight){
    temp=dq.pollFirst();
    if(temp.left!=null){
    dq.offerLast(temp.left);
    next++;
    }
    if(temp.right!=null){
    dq.offerLast(temp.right);
    next++;
    }
    }
    else{
    temp=dq.pollLast();
    if(temp.right!=null){
    dq.offerFirst(temp.right);
    next++;
    }
    if(temp.left!=null){
    dq.offerFirst(temp.left);
    next++;
    }
    }

    list.add(temp.val);

    if(–current==0){
    result.add(list);
    list=new ArrayList();
    leftToRight=!leftToRight;
    current=next;
    next=0;
    }
    }
    return result;
    }

    VN:F [1.9.22_1171]
    0
  16. Pingback: Must read problems of LeetCode | What I learn, I blog !

  17. Pingback: Printing a Binary Tree in Zig Zag Level-Order | This is how Cheng grows up

  18. Pingback: Idea Board Printing a Binary Tree in Zig Zag Level-Order | Idea Board

  19. muma

    One Queue And One Stack

    void PrintZigZag(BNode* pRoot)
    {
    if(pRoot == NULL)
    return;
    int level = 1;
    std::queue Q;
    std::stack S;
    Q.push(pRoot);
    Q.push(NULL);
    while(Q.size() != 0)
    {
    BNode* pNode = Q.front();
    Q.pop();
    if(pNode == NULL)
    {
    level++;
    printf(“\n”);
    while (S.size() != 0) {
    BNode* newNode = S.top();
    S.pop();
    Q.push(newNode);
    }
    if(Q.size() != 0)
    {
    Q.push(NULL);
    }
    }
    else
    {
    printf(“%d “, pNode->data);
    if(level % 2 == 1)
    {
    if(pNode->left)
    S.push(pNode->left);
    if(pNode->right)
    S.push(pNode->right);
    }
    else
    {
    if(pNode->right)
    S.push(pNode->right);
    if(pNode->left)
    S.push(pNode->left);
    }
    }
    }
    }

    VN:F [1.9.22_1171]
    0
  20. Gaurav Agarwal

    I simply achieved it using deque .

    public void printZigZagLevel(){
    ArrayDeque<Tree> theQueue = new ArrayDeque<Tree>();
    theQueue.add(this);
    int nodeInCurrentLevel = 1;
    int nodeInNextLevel = 0;
    int level = 1;
    System.out.print(“level:0 “);
    Tree currentNode = null;
    boolean forward = false;
    while(true){
    if(forward)
    currentNode = theQueue.removeFirst();
    else currentNode = theQueue.removeLast();
    nodeInCurrentLevel–;
    System.out.print(currentNode.root.toString());
    if(forward){
    if(currentNode.lTree!=null){
    theQueue.addLast(currentNode.lTree);
    nodeInNextLevel++;
    }
    if(currentNode.rTree!=null){
    theQueue.addLast(currentNode.rTree);
    nodeInNextLevel++;
    }
    }
    else {
    if(currentNode.rTree!=null){
    theQueue.addFirst(currentNode.rTree);
    nodeInNextLevel++;
    }
    if(currentNode.lTree!=null){
    theQueue.addFirst(currentNode.lTree);
    nodeInNextLevel++;
    }
    }
    if(theQueue.isEmpty()) break;
    if(nodeInCurrentLevel==0){
    if(forward) forward = false;
    else forward = true;
    System.out.println();
    System.out.print(“level:”+level+++” “);
    nodeInCurrentLevel = nodeInNextLevel;
    nodeInNextLevel = 0;
    }
    }
    }

    VA:F [1.9.22_1171]
    0
  21. Zhanrui.Liang

    Here’s my solution .

    VN:F [1.9.22_1171]
    0
  22. Pingback: LeetCode | Technical interview solutions

  23. Mehul

    Here is a solution which uses one stack and two counters for counting the number of nodes in the current level and in the next level

    VA:F [1.9.22_1171]
    0
  24. agentaruhan.in

    Football odds and Baseball odds will depend a lot not only on the performance of the team and
    individual players but also on the location of the game. Web based Baccarat – Most of the time
    the player displays there bet prior to every card can be aquired.

    No hidden terms or rules; no confusion; just a cent percent risk-free and sober betting.

    VA:F [1.9.22_1171]
    0
  25. cara daftar bpjs

    If so you will need to get a comprehensive package in order to cover your vehicle.

    If you have a serious accident, for example, you may receive treatment for free in a public hospital.

    It is also recommended to look for rate guarantee in order to protect your family,
    since the health insurance plans can change in time.

    VA:F [1.9.22_1171]
    0
  26. Fang

    2
    / \
    4 7
    / \ \
    6 3 9
    / \ \
    1 5 8

    list[0] = 2
    list[1] = 7,4
    list[2] = 6,3,9
    list[3] = 8,5,1

    VA:F [1.9.22_1171]
    0
  27. madden15-coins.com

    Hello Your main web site starts up honestly slow for
    me, I am not sure who’s problem is that but flickr
    opens up pretty quick. However , thanks for writing superb article.

    I believe this has already been honestly useful
    to visitor who click here. I personally need to point out that you actually
    have done amazing work with this plus hope to discover many more wonderful
    stuff through you. Soon after checking out the post, I have book-marked your web site.

    VA:F [1.9.22_1171]
    0
  28. Allen

    Have you herd of systems in adding best divorce lawyer in more items increases the demand for artistc glassware.
    You may wish to target women but then they might find antique jewelry can be used to.

    VA:F [1.9.22_1171]
    0
  29. Walpole Interior Designer

    Thhe extra you recognize, the highyer off you’ll be.
    Consider looking towards future tendencies equivalent to inhabitants progress, designing for the elderly, fashionable structure and iinexperienced design; traaining inside these specific fields of
    desugn gives you the upper hand within the job market.

    VA:F [1.9.22_1171]
    0
  30. RI stone exteriors

    Roofers for essentially the most half will quote you prices on a cost per sq.
    foot” aand most dependable corporations will probably be in the same rice once you start getting estimates.

    VA:F [1.9.22_1171]
    0
  31. michael maloney

    This can not solely put a crimp in your holiday plans as you’re arrested, tzken to jail and booked nto the
    felony justice system, however it will probably also
    have a major influence on the remainder of your life ince a DUI can lead
    to a prisonn conviction, a legal record, jail time, thhe suspension of you drivers
    license and huge fines.

    VA:F [1.9.22_1171]
    0
  32. Toronto Limo VIP

    We dtermined that night time to ggo after thuis contract as a dual company enterprise, Max & Me Catering
    doing the particular occasion food andd Festival Food Management handling the museum cafe iin addition to the special event alcohol service too makoe the revenue break up more
    equal and allow evcery entity to specialize within the
    side that that they had extraa experience in.

    VA:F [1.9.22_1171]
    0
  33. Blog writing

    As commercial of the enterprise firm at all times provide wholesome and fruitful outcomes inn the type of excessive volume of sale, productivity and earnings, enterprise firms always look ahead to writing articles forr promotion of their corporations so tuat most people get aware about
    their firrm and increase heir clientele.

    VA:F [1.9.22_1171]
    0
  34. gemmes clash royale

    Greetings from Idaho! I’m bored to tears at work so I decided to check out your
    site on my iphone during lunch break. I enjoy the info you provide here and can’t wait to take a look
    when I get home. I’m shocked at how quick your blog loaded
    on my phone .. I’m not even using WIFI, just 3G .. Anyhow, awesome site!

    VA:F [1.9.22_1171]
    0
  35. Randy

    Instead, always be looking out for special events in a client’s life that would warrant a small corporate reward as a tokenn of
    your thoughtfulness and good needs.

    VA:F [1.9.22_1171]
    0
  36. Sylvia

    Every single certainly one of these people had cash on their
    minds; not to make the most effective skin cream on the market, and to
    not mention taking the lives of animals.

    VA:F [1.9.22_1171]
    0
  37. Michelle

    If you find yourselff printing less and needing frwer copies, you might not even get the volume discounts you probably did prior to now, which makes
    yyour per copy prices higher.

    VA:F [1.9.22_1171]
    0
  38. Rowena

    The elements which are accountable in growing ovarian cysts are
    that the follicles that are purported to launch the egg just
    keep growing and turn into purposeful cysts.

    VA:F [1.9.22_1171]
    0
  39. Arnette

    They also camje up with another funnmy line,
    this might be one thing you must see at the end of a financial business on the
    CNBC morning stock market report; “The place we measure your financial success one day at a time.” And actually is not that aboht how a gambler thinks, uup
    in the future aand down the subsequent – or how abolut somebody that’s going via Alcoholics Nameless,
    that complete; “sooner or later at a time,” factor.

    VA:F [1.9.22_1171]
    0
  40. Dominic

    Universities and sports activities clubs are common spenders on this space of company reward merchandising choosing objects such
    because the lead crystal whiskey glass supplied in an outstanding satin-lined presentation box, as a
    corporate reward opportunity for hiis or her alumni or club members.

    VA:F [1.9.22_1171]
    0
  41. bluedart

    Display screen wash is a vital working in immediately’s air and atmosphere.
    Preserve it topped up. Gone arre the das while you did not want to fireplace up your display wash more than once a month.

    VA:F [1.9.22_1171]
    0
  42. uidaadhar

    There is little question the opinions of these towards however for the legalization of marijuana have raised because the Controlled Substances Act was modified
    in 1972.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*