'Time limit exceeded in GeeksForGeeks zig zig traversal in tree

I am working on the GeeksForGeeks ZigZag Tree Traversal problem:

Given a Binary Tree. Find the Zig-Zag Level Order Traversal of the Binary Tree.

Example 1:

Input:

    3
  /   \
 2     1

Output:

3 1 2

Example 2:

Input:

          7
       /     \
      9       7
    /  \     /   
   8    8   6     
  /  \
 10   9

Output:

7 7 9 8 8 6 9 10

I am getting a Time Limit Exceeded error.

My approach is to push a NULL for each different level, and at every NULL I am changing the direction:

vector<int> ans;
queue<Node*> q;
q.push(root);
q.push(NULL);
int k = 1;

while (q.size() > 0)
{
    Node * top = q.front();
    q.pop();
    if (!top)
    {
        k = 1 - k;
        q.push(NULL);
        continue;
    }
    ans.push_back(top->data);
    if (k)
    {
        if (top->right)
            q.push(top->right);
        if (top->left)
            q.push(top->left);
    }
    else
    {
        if (top->left)
            q.push(top->left);
        if (top->right)
            q.push(top->right);
    }   
}

Why is this code not finishing in time?

c++binary-search-treetraversal


Solution 1:[1]

The issue that causes the time out is related to the NULL you keep on the queue. That means the queue will never get empty. If you pop a NULL and the queue becomes empty, you still push a new NULL unto it so your loop never ends.

You could fix this by changing the while condition to q.size()>1, but then still there is a flaw in the algorithm:

When visiting the nodes in a level from left to right, you correctly put the right child first in the queue, and then the left child, but this only reverses the direct children. The cousins are still relating to eachother in the left-to-right order, which is wrong.

I would suggest to use two vectors instead of one queue, and let those vectors alternate.

Here is how your code would need to be adapted:

    vector <int> zigZagTraversal(Node* root)
    {
        vector<int> ans;
        vector<Node*> parents;
        vector<Node*> children;
        children.push_back(root);
        int k = 0;

        while (children.size() > 0)
        {
            k = 1 - k;
            parents = children;
            children.clear();
            while (parents.size() > 0)
            {
                Node * top = parents.back();
                parents.pop_back();
                ans.push_back(top->data);
                if (top->right && k == 0)
                    children.push_back(top->right);
                if (top->left)
                    children.push_back(top->left);
                if (top->right && k == 1)
                    children.push_back(top->right);
            }
        }
        return ans;
    }

Solution 2:[2]

@trincot

thankyou for your help

I got it where I am making mistake.

I should check the size of queue before pushing NULL Because, at time of last NULL (what the code is doing poping NULL , check it ooh it is NULL then again push a NULL and continue doing it)

so, I have to check the size of queue at the time of pushing NULL if it is zero have to break the loop

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 trincot
Solution 2

Related Questions