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();
level.add(current.val);
if(isEvenLevel){
if(current.left != null) deq.add(current.left);
if(current.right != null) deq.add(current.right);
}else{
if(current.right != null) deq.addFirst(current.right);
if(current.left != null) deq.addFirst(current.left);
}
}
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) {
Queue<Node<Integer>> queue = new LinkedList<>();
queue.add(root);
List<List<Integer>> output = new LinkedList<>();
boolean leftToRight = true;
while (!queue.isEmpty()) {
int curLevelSize = queue.size();
LinkedList<Integer> curList = new LinkedList<>();
for (int i = 0; i < curLevelSize; i++) {
Node<Integer> curNode = queue.poll();
if (leftToRight)
curList.addLast(curNode.val);
else
curList.addFirst(curNode.val);
if (curNode.left != null)
queue.add(curNode.left);
if (curNode.right != null)
queue.add(curNode.right);
}
leftToRight = !leftToRight;
output.add(curList);
}
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);
else newlevel.addFirst((Integer)node.val);
That extra line saves so much more in terms of computational power.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();
levelList.add(node.val);
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);
}
}
resultList.add(levelList);
}
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<>();
queue.add(root);
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)
currLevel.add(node.val); // Standard adding of nodes to currLevel list
else
currLevel.add(0, node.val); // Adds to front of currLevel list (reverses it)
if (node.left != null)
queue.add(node.left); // Adds left child to queue
if (node.right != null)
queue.add(node.right); // Adds right child to queue
}
reverse = !reverse; // Flips boolean value
results.add(currLevel);
}
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