A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Today we are going to discuss how to do a level order traversal of Binary Tree.
The Problem
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Example 1
1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2
1
2
Input: root = [1]
Output: [[1]]
Example 3
1
2
Input: root = []
Output: []
The Solution
To do a level order traversal of a binary tree, the first option would be to do a Breadth-First approach. Let’s go ahead and do that on example number 1 check the output. The output for that will be [3,9,20,15,7] but the result need is slightly different which is [[3],[9,20],[15,7]]. This means that at every level during the Breadth-First Traversal, we should initialise a new array and store the elements in that level only in that array. To solve this question in such a method,
- Store the elements to the queue starting with the root.
- With each queue element processing, we find the queue length, initialise an empty array and queueCount to zero.
- Inside the queue processing while loop let’s run another while to see if the element is an element from the current level of the tree. If yes it will be added to the newly created empty array or else the entire array will be added to the final result array.
JavaSript implementation of this will be,
The run time complexity of this implementation will be O(n).
References