102. Binary Tree Level Order Traversal

Prompt

You’re given the root of a binary tree and it’s your task to return the level order traversal of the values of the nodes within the tree (from left to right, level by level).

Approach

The approach to this problem is testing your fundamental knowledge of breadth-first search or what’s also known as level order traversal. As opposed to its counterpart of looking as deep as you can go (depth-first search), breadth-first search examines a tree layer by layer or level by level typically in the order from left to right.

Though it makes more sense to write the code recursively when writing a traversal algorithm for DFS, this is not the case when the traversal algorithm for BFS. Instead, we commonly write our level order traversal code iteratively using an auxiliary data structure called a Queue.

Using a Queue is ideal when performing a level order traversal because a Queue is a FIFO data structure in which the first element you insert into the data structure also serves as the first element that gets ejected or removed from it.

In the first iteration, we add our root node into the Queue where we eventually remove it and add its left and right child into the Queue. We do the same for every node from left to right in every level of the tree.

For this particular problem, we want to make sure to store all of our nodes’ values into an empty array that we will eventually return once our algorithm has finished running. This is because the output that the problem expects is an array containing a subarray for each level containing the nodes’ values of that respective level.

Code

In Python, we import deque from the collections module of the Python standard library. Using deque allows us to create a double-ended Queue in Python which allows us to have access to using special methods such as .popleft() that allows us to remove an element from the left hand side of a Queue not in linear but in constant time.

Python

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com