Repeat Code with LeetCode: Binary Tree Level Order Traversal

When it comes to data structures, it is really important to not mistake the forest for the trees. We studied trees in college, but then I had to leave.

Sometimes I say that from personal experience, trees do not come up in interviews nearly as often as you might expect — but there are two reasons why this anecdotal knowledge may be misleading. First, I have not done many final interviews; it is possible that they come up a lot more often in final rounds than introductory coding tests. Second, there was a time I really needed “tree knowledge” but did not have it in my pocket.

In my college, they loved to talk about the theory of things. We would learn about breadth first search, but maybe instead of coding we would simply fill out some definitions, or even write out the order of which nodes were processed when. LeetCode tree problems are arguably just theoretical as well, but with LeetCode you can actually write code that traverses trees.

You can learn a lot of theory and definitions without necessarily being able to solve a problem like this. For starters, the syntax can take some getting used to.

The Problem

Problem: Binay Tree Level Order Trave

Difficulty: Medium

Topics Covered: Breadth First Search (BFS), Trees, Queues

Description: 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).

Find this on my personal GitHub here, and please ignore all the rejected submissions…and the fact that I apparently attempted this several months ago and then forgot about it.

First Digression: Dealing with Pointers in LeetCode

It seems like everyone solves these questions in Java or Python, so frequently that it may actually put C++ users at a disadvantage. That being said, the C++ syntax is not too different from its Java counterpart. C++ users just love the arrow, which you will be seeing left and right on these (in lines 39 and 41 above, for example). The arrow is just the rough equivalent of the dot operator for pointers — you can get away with using the dot operator, but doing so could get confusing.

Here, LeetCode gives us the root of the tree. If you are new to this, and if your heart so desires, you can test print the root’s value or its children. Lots of LeetCode problems involving trees and linked lists structure their format in a similar manner.

The Code

Here I include a sarcastic number of comments.

I made an exciting discovery while researching this problem…they have a Back to Back SWE YouTube video on it! My personal belief is that Back to Back SWE videos > Kevin Naughton videos, and in turn Kevin Naughton videos > Nick White videos. The tradeoff is that Nick White has the most content and BackToBack really lacks content; had it not been for this, BackToBack would probably be the supreme authority for interview prepration.

After maybe a 30 minute attempt of the problem — do what I say, not what I did — this is a good “overview video” of breadth first search. It does not go over any code, and that they did not put code in the description is a pet peeve of mine, but it does the best job explaining breadth first search.

From BackToBack SWE:

• Identify that a tree is just a type of graph
• Identify that this problem is best solved with a breadth first search
• Because this problem is best solved with a breadth first search, we use a queue (as opposed to a depth first search, in which we can use a stack)
• For each element in the queue, add the let and right children

I think of a breadth first search as a “don’t go deep all at once algorithm,” and a depth first search as a “go as deep as you can before moving on” algorithm. That is how sophisticated my explanation was in an actual interview, which may have contributed to my not getting the job.

Decription from HackerEarth:

There are many ways to traverse graphs. BFS is the most commonly used approach.

BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

As the name BFS suggests, you are required to traverse the graph breadthwise as follows:

1. First move horizontally and visit all the nodes of the current layer
2. Move to the next layer

Here is Kevin N. talking through the Java code mine was based on. I mean stolen from. Wait, no, I had it right the first time…

He told me that if I watched this five-minute video, I would never be confused about BFS again. Press X to doubt

The code I wrote above…well, the good news is that it is only 25 lines long. It has a vector of vectors of integers, which can be confusing (the nested structure is a requirement). It also uses a vector of pointers, which is not that confusing considering that the problem is already dealing with pointers to represent a tree. The way Kevin N describes it, you can imagine yourself running a restaurant. Your restaurant has a line of people, or queue. As long as there are people in the queue, you continue to have to process them.

Another thing I discovered while writing this is that Vaidehi Joshi is now actively writing again. That is great news. Anyway, she provides more about tree here, and more about breadth first search here. The number of puns she manages is astounding.

BFS is also one of the patterns in Educative.io’s Grokking the Coding Interview series, but unlike “Two Pointers” or some of the other patterns it is actually a very well-known technique that you can expect interviewers to be familiar with.

Closing Thoughts

I am actually a big fan of Algorithms to Live By, a book that achives the rare feat of combining computer science with self-help. What did they have to say about BFS? I do not recall, but they may have applied it to learning.

My way of studying for midterms/final exams was like a breadth first search. I would write out a list of topics, and I would just do surface-level studying. Then, in the event that I finished and there was time remaining, I would begin to dig deeper only after I studied all the critical topics.

Is this a good way to study in college? Probably not. But it won for Metaphor Potential.