Today we are going to solve two DS problems that are actually very similar.
They are respectively :-
And I like to solve them in a specific way which comes natural to me.
Binary Tree Level Order Traversal
Here is the code which works :-
var levelOrder = function(root) {
if(!root)
return [];
let currentQueue = [];
let nextNodes = [];
const output = [[root.val]];
currentQueue.push(root);
while(currentQueue.length){
const node = currentQueue.shift();
nextNodes = nextNodes.concat(findNextNodes(node));
if(!currentQueue.length && nextNodes.length){
currentQueue = nextNodes;
nextNodes = [];
output.push(currentQueue.map(node=>node.val));
}
}
return output;
};
const findNextNodes=(node)=>{
const nextNodes = [];
if(node.left){
nextNodes.push(node.left);
}
if(node.right){
nextNodes.push(node.right);
}
return nextNodes;
}
Explanation :-
- First we check whether
root of binary tree exists or not. If not, simply return empty array [].
- Initialize a
currentQueue and nextNodes array.
- Initialize a
output 2D array where for each level we maintain an array consisting of the level nodes. Initially, the [root.val] will be the first valid entry. So output will be [[3]].
- And then push the current
root node inside currentQueue. So currentQueue will be [Node(3)].
- Now, we will loop over the
currentQueue until it is empty.
- Being a queue, we dequeue the first entry in it using
shift operator on currentQueue.
- Now, we pass this entry or
node(Node(3)) inside findNextNodes function whose purpose it to return us a list of children of the passed node.
findNextNodes initializes an empty nextNodes array and pushes the left and right children of node if they exist and returns the nextNodes array. nextNodes will be [Node(9),Node(20)].- Then the returned array is concatenated with
nextNodes. nextNodes will be [Node(9),Node(20)].
- Now before the end of the loop, if
currentQueue is empty and nextNodes is not, currentQueue starts referring the nextNodes array and nextNodes is reinitialized to []. Also, all the node.val values in the currentQueue are pushed in the form of an array to output. By this step, output will be [[3],[9,20]].
- This way the for each level we will successfully obtain the left to right level order traversal in the
output array.
Binary Tree Zigzag Level Order Traversal
Before we see the code and explanation, it's important to note that we will be converting the above solution to obtain the current one. I would like to stress on this derivation because this is how I particularly enjoyed the process of arriving at this solution. We will do it in two iterations so that the process of arriving at this solution seems more intuitive.
Alright, here is the first iteration :-
var zigzagLevelOrder = function(root) {
if(!root)
return [];
let currentQueue = [];
let nextNodes = [];
let isNextLevelEven = true;
const output = [[root.val]];
currentQueue.push(root);
while(currentQueue.length){
const node = currentQueue.shift();
nextNodes = nextNodes.concat(findNextNodes(node,isNextLevelEven));
if(!currentQueue.length && nextNodes.length){
currentQueue = nextNodes;
nextNodes = [];
isNextLevelEven = !isNextLevelEven;
output.push(currentQueue.map(node=>node.val));
}
}
return output;
};
const findNextNodes=(node,isNextLevelEven)=>{
const nextNodes = [];
if(node.left){
nextNodes.push(node.left);
}
if(node.right){
nextNodes.push(node.right);
}
return isNextLevelEven?nextNodes.reverse():nextNodes;
}
Explanation :-
- As soon as you see the above code, you will realize that all it does is add subtle nuances to level order traversal's code.
- The first nuance is the
isNextLevelEven variable. So let's discuss it. When we think about a zigzag traversal, it starts on level 1 i.e. root node from left to right and then on level 2 from right to left and the again from left to right on level 3. So there is a alternating state that's being introduced. Alternating state can be depicted using a boolean and that's what we are doing here. If root is level 1 i.e. an odd level, then the next level would be even. This is why I have initialized isNextLevelEven to true in the starting of this code.
- Before the start of the loop,
output will be [[3]] and currentQueue will be [Node(3)].
- Now, we will loop over the
currentQueue until it is empty.
- Being a queue, we dequeue the first entry in it using
shift operator on currentQueue.
- Now, we pass
node(Node(3)) and isNextLevelEven inside findNextNodes function whose purpose it to return us a list of children of the passed node according to isNextLevelEven boolean variable.
findNextNodes like before initializes an empty nextNodes array and pushes the left and right children of node if they exist. The change comes in the returning value step where now exists a ternary condition where isNextLevelEven if true will return the reversed nextNodes (for right to left) array else the nextNodes (for left to right) as it is . In this step, since isNextLevelEven is true, the returned value will be [Node(20),Node(9)].- Then the returned array is concatenated with
nextNodes. nextNodes will be [Node(20),Node(9)].
- Now before the end of the loop, if
currentQueue is empty and nextNodes is not, currentQueue starts referring the nextNodes array and nextNodes is reinitialized to []. We also flip the isNextLevelEven boolean. Also, all the node.val values in the currentQueue are pushed in the form of an array to output. By this step, output will be [[3],[20,9]].
- The algorithm seems reasonable till here. But let's see what happens in next iteration of while loop.
- Now
currentQueue being [Node(20),Node(9)], node will be Node(20) due to shift operation.
- Now since next level is 3 which is odd,
[Node(15),Node(7)] will be concatenated with nextNodes.
- And again in next iteration of while loop,
node will be Node(9) due to shift operation resulting in nextNodes being [Node(15),Node(7),Node(23),Node(43)].
- Now when the
if condition inside the while loop holds true, output will become [[3],[20,9],[15,7,23,43]] which clearly is wrong because the last level is not traversed from left to right as we wanted to.
The step where we went wrong here is assuming that currentQueue well has to be a queue. Being a queue, we will never be able to start a traversal from the last element. For instance, after we got correct output till level 2, we would have wanted, that for level 3, first the children of Node(9) were pushed from left to right and then for Node(20) but instead the reverse happened. This is literally how I formed the second intuition that it's my last element from which the next level of nodes should be traversed. And the Data Structure which operates primarily on the last element is none other than a stack.
So all we need is to replace the shift operation with pop and things will work as we intend to. Obviously, it's better to rename currentQueue to currentStack for brevity.
So here is the working code :-
var zigzagLevelOrder = function(root) {
if(!root)
return [];
let currentStack = [];
let nextNodes = [];
let isNextLevelEven = true;
const output = [[root.val]];
currentStack.push(root);
while(currentStack.length){
const node = currentStack.pop();
nextNodes = nextNodes.concat(findNextNodes(node,isNextLevelEven));
if(!currentStack.length && nextNodes.length){
currentStack = nextNodes;
nextNodes = [];
isNextLevelEven = !isNextLevelEven;
output.push(currentStack.map(node=>node.val));
}
}
return output;
};
const findNextNodes=(node,isNextLevelEven)=>{
const nextNodes = [];
if(node.left){
nextNodes.push(node.left);
}
if(node.right){
nextNodes.push(node.right);
}
return isNextLevelEven?nextNodes.reverse():nextNodes;
}
The second question was asked to me in a startup's interview in early stage of my career. That time I didn't know JS and was interviewing for a Java Dev position. I didn't do well in that interview and kind of dreaded this problem. Later one day while solving the level order traversal on leetcode, I realised that the zigzag problem is an extension of this and then implemented it in same manner as I documented in this article. That connection between both problems was cool to arrive at.
Thank you for your time :D
