Solve Leetcode Problems and Get Offers From Your Dream Companies

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.

Motivation to learn algorithms

Solve Leetcode Problems and Get Offers From Your Dream Companies

Problem Statement

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:

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

Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1] 

Output: [[1]] 

Example 3:

Input: root = [] 

Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].

• -1000 <= Node.val <= 1000

Youtube Discussion

Solution

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.

1. Create an empty queue q

2. temp_node = root

3. Loop while temp_node is not NULL

   a. print temp_node->data.

   b. Enqueue temp_node’s children(from left to right)

   c. Dequeue a node from q.

   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

C++ Solution

Java Solution

Complexity Analysis

The time complexity is O(n)

The space complexity is O(n)

Thank You for reading and Follow this publication for more LeetCode problems!😃

LeetCode Simplified
50+ Data Structure and Algorithms Interview Questions for Programmers