102. Binary Tree Level Order Traversal
Leetcode #: 102
Name: Binary Tree Level Order Traversal
Companies asked: Amazon, Apple, Google, Meta, Microsoft
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).
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.
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.
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.
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 firstname.lastname@example.org