Problem 102. Binary Tree Level Order Traversal
In this series, I am going to solve Leetcode medium problems live with my friends, which you can see on our youtube channel, Today we will do Problem Leetcode: 102. Binary Tree Level Order Traversal.
A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.
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).
Input: root = [3,9,20,null,null,15,7] Output: [,[9,20],[15,7]]
Input: root =  Output: []
Input: root =  Output: 
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
This is one of the standard coding problems on Binary Tree, in this problem we have to return the level order traversal of its nodes' values. (i.e., from left to right, level by level). This can be done by using BFS on the tree with help of a queue. For each node, first, the node is visited and then its child nodes are put in a FIFO queue.
Create an empty queue q
temp_node = root
Loop while temp_node is not NULL
The following code implements this algorithm
You can learn more about BFS in this tutorial
How to use Breath Fast Search Pattern for craking coding Interviews
The time complexity is O(n)
The space complexity is O(n)