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.
Create an empty queue q
temp_node = root
-
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
Top comments (0)