# Binary Tree ZigZag Level Order Traversal - Breadth First Search / BFS on Tree

For JavaScript solution, reverse() is an expensive method since it essentially swap every element of the array. If the queue is long, it may have performance issue. A better way is to construct the level array correctly every time.

``````    const queue = [];

queue.push(root);
let level = 0;

while(queue.length > 0) {
const n = queue.length;
const levelArr = new Array(n);

for(let i = 0; i < n; i++){
const curNode = queue.shift();
if(level % 2 === 0) {
levelArr[i] = curNode.val;
} else {
levelArr[n - i - 1] = curNode.val;
}

if(curNode.left) queue.push(curNode.left);
if(curNode.right) queue.push(curNode.right);
}
result.push(levelArr);
level++;

}

return result;`````````

I avoided the Collections.Reverse by taking advantage of the deque properties

Here is the main logic for the srategy

boolean isEvenLevel = res.size() % 2 == 0;

``````        for(int i = 0; i < elementsInLevel; i++){
Node<Integer> current = isEvenLevel ? deq.removeFirst() : deq.removeLast();

if(isEvenLevel){
}else{
}
}
``````

instead of reversing the array, you can alternate between `pushing` the node values into the response and `unshifting` them.

``````function zigZagTraversal(root) {
const q = [root]
const res = []
let reverse = false
while (q.length) {
let n = q.length
let curr = []
for (let i = 0; i < n; i++) {
let node = q.shift()
if (node) {
reverse ? curr.unshift(node.val) : curr.push(node.val)
q.push(node.left)
q.push(node.right)
}
}
if (curr.length) res.push(curr)
reverse = !reverse
}
return res;
}
``````

This solution is fine. There is a better answer though that intuitively uses a data structure. Do a level order traversal, but use a stack instead of a queue. Then all you have to do is add the children to the stack in the appropriate way based on a reverse boolean.

Best sol, thanks

I used the push and pop feature of deque to put then in zig zag order
def zig_zag_traversal(root: Node) → List[List[int]]:
res = []
q = deque([root])

``````while q:
level = []
for i in range(len(q)):

if len(res) % 2 == 0:
node = q.popleft()
if node:
level.append(node.val)
q.append(node.left)
q.append(node.right)
else:
node = q.pop()
if node:
level.append(node.val)
q.appendleft(node.right)
q.appendleft(node.left)
if level:
res.append(level)

return res
``````

@Daniel great solution. I used a variable called reverse and just flipped reverse after each level but keeping track of the level itself works too.

An alternative solution in Java is to use LinkedList’s specific methods for adding at the head of each list

``````public static List<List<Integer>> levelOrderTraversal(Node<Integer> root) {

boolean leftToRight = true;
while (!queue.isEmpty()) {
int curLevelSize = queue.size();
for (int i = 0; i < curLevelSize; i++) {
Node<Integer> curNode = queue.poll();
if (leftToRight)
else

if (curNode.left != null)

if (curNode.right != null)
}
leftToRight = !leftToRight;
}
return output;
}
``````

Using Collections.reverse is going to be costly especially if you have a huge tree.
You might be looking at a dense tree where most of the data is at the leaves.

A better alternative, as many suggested, is to reverse the level as we dequeue the node from the queue.

All you need to do is to take off the Collections.reverse() from the solution and instead of just adding node.val to the newLevel:

``````                if (!leftToRight) newlevel.add((Integer)node.val);

That extra line saves so much more in terms of computational power.``````
1 Like

Structured Programming JS Solution

``````function zigZagTraversal(root) {
const result = [];
const queue = [root];

while (queue.length > 0) {
const n = queue.length;
const newLevel = [];

for (let i = 0; i < n; i++) {
const node = queue.shift();
const action = result.length % 2 != 0
? "unshift"
: "push";

newLevel[action](node.val);

for (const child of [node.left, node.right]) {
if (child) queue.push(child);
}
}

result.push(newLevel);
}

return result;
}
``````

How about if we have to really visit the nodes in zig zag manner. I used two stacks to perform the same operation. even though this seems little lengthy code, its pretty straightforward.
public static List<List> zigZagTraversal(Node root) {
List<List> resultList = new ArrayList<>();
Stack<Node> sL2R = new Stack<>();
Stack<Node> sR2L = new Stack<>();
sL2R.push(root);
while(!sL2R.isEmpty() || !sR2L.isEmpty()){
Stack<Node> a = null;
Stack<Node> b = null;
if(!sL2R.isEmpty()){
a= sL2R;
b= sR2L;
}else{
a= sR2L;
b= sL2R;
}
ArrayList levelList = new ArrayList<>();
while(!a.isEmpty()){
Node node = a.pop();
if(sL2R.isEmpty()){
if(node.left!=null)b.push(node.left);
if(node.right!=null)b.push(node.right);
}else{
if(node.right!=null)b.push(node.right);
if(node.left!=null)b.push(node.left);
}
}
}

``````    return resultList;
}
``````

Really great answer Daniel. I think this site is a bit lagging behind better teaching material.

Really great answer Daniel. I think this site is a bit lagging behind better teaching material.

yea you can do taht too

you are right, we updated the code

is line 16 supposed to be new_level = [ ] instead of queue()?

appendleft requires new_level to be a deque

Hi all, I found the solution to be a bit confusing, so after some tinkering I came across this solution for Java… it doesn’t use Collections.reverse(), it uses a normal ArrayList for the current level, and provides some notes. Hopefully it helps!! (This is my first comment on a problem, so apologies if there are any crazy formatting issues).

``````public static List<List<Integer>> zigZagTraversal(Node<Integer> root) {
List<List<Integer>> results = new ArrayList<>();
ArrayDeque<Node<Integer>> queue = new ArrayDeque<>();
boolean reverse = false; // Flag to determine if we reverse a row

while (!queue.isEmpty())
{
int size = queue.size();
ArrayList<Integer> currLevel = new ArrayList<>();

for (int i = 0; i < size; i++)
{
Node<Integer> node = queue.pop(); // Gets node from queue, removes from queue
if (reverse == false)
else

if (node.left != null)
if (node.right != null)
}

reverse = !reverse; // Flips boolean value
}

return results;
}
``````

I used a counter and reversed every other, this was easier for me to grasp

def zig_zag_traversal(root: Node) → List[List[int]]:
res =
q = deque([root])
count = 1
while q:
lev =
for _ in range(len(q)):
node = q.popleft()
lev.append(node.val)
for child in [node.right, node.left]:
if child:
q.append(child)
if count % 2 == 0:
res.append(lev)
else:
res.append(lev[::-1])
count += 1
return res