Level Order Traversal of Binary Tree in Javascript (Recursive)

In this post I’ll be going through one possible implementation of a level order traversal of a binary tree using Leetcode problem 102 Binary Tree Level Order Traversal.

First, what is a level order traversal? A level order traversal is a tree traversal in which you process all nodes of a tree by depth: first the root, then the children of the root, etc. (source: https://xlinux.nist.gov/dads/HTML/levelOrderTraversal.html). In other words, it is a breadth first search starting at the root.

You can see in the below example, the root is the first level, then its two leaves (9 and 20 in the example), are the next level down and below that (15 and 7 comprise the next level). Any children of the root with the value of 9 would be on the same level as the nodes with values 15 and 7.

source: leetcode

For this example, the input and output are below. You can see in the output that the index of each level of nodes corresponds with the level number (with the root node being level 0).

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

I mentioned this is a breadth first search. A breadth first search is typically implemented using a queue data structure (as opposed to a stack or recursive function for a depth first search), however for this solution I will be using a recursive function as that method is more intuitive to me than a queue-based approach.

For this solution, the indexes of the output correspond with the level of the tree. So, in the above example you see that the array containing the root is at index 0, the array containing the nodes for level 2 is at index 1 etc.

With this, we can create a recursive function that takes (1) the node being processed and (2) the level number, with the first call starting at level 0, and for each subsequent recursive call incrementing the level by 1 so that each node gets added to the correct index in the output. This is a little confusing to describe, so I’ll show full code here:

So what is going on in the above?

• First, we initialize our result output to an empty array.
• Next, starting on line 4 of the above, we initialize our recursive function with the node and level (when we first call this function you will see that we call it with the root node, and initial level 0).
• In the function, our break condition is if a node returns a falsey value (i.e. we have reached the end of a particular node path, because we have passed the function a null value).
• Next (line 7), we check if our result function current has an array at the index corresponding with our current level. If it does, we push the value of our current node onto that array within the result array. If the result array does NOT have an array at the index corresponding with the current level we simply create a new array containing the value of our node.
• The last lines of this recursive function are where it comes together. Here we call the recursive function twice: once with the left child of the current node, and once with the right child. With both of these calls, we pass our level argument as current level + 1. This way, with subsequent calls, all nodes on the same level will have the same level number passed as their argument. The level property basically functions as a counter for the depth of the tree.

With this implementation of the level order traversal and the idea of progressively implementing our level counter, you can tackle Leetcode’s problem 103 (Binary Tree Zigzag Level Order Traversal) using a similar method.

Hope this helps!