Binary Tree Level Order Traversal - Drawing The Parallel Between Trees & Graphs

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: You are given the root node of a binary tree. Return a list consisting of each level of the tree (we will have a list of lists, a list for each level's items), where each level is traversed from left to right. A level order traversal.

What Do We Know?

We know our preorder, inorder, and postorder traversals...but this is a little different.

We want to go level by level here...what does this remind us of?

Every acyclic connected graph is a tree, and all trees are acyclic connected graphs.

This unlocks our ability to search a tree list we search a graph, using Breadth First Search and Depth First Search.

DFS will go deep, and BFS will go out level by level. We want BFS since it is a more natural approach to something like this.

We realize that this is just the breadth-first search of a tree structure.

We shift our knowledge from graph search to this problem.

Complexities

n is the total amount of nodes in the binary tree

Time: O( n )

Space:

With output: O( n ) because we will store n nodes in the list of levels structure.

Without output: O( n ) the queue at maximum at any point in time will hold some fractional component of the total nodes in the tree.

The fractional constant disappears and the asymptotic behavior is linear.

We can't bound the max space in the queue to the widest level because when we process the widest level...if there is a level below it we will have all the nodes from the widest level PLUS what we are adding into the queue as we process each node in the level (we remove 1 node and can add 2 children which will push us past the size of the widest level initially).

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

Table of Contents:

A Quick Message 0:00 - 1:01
The Problem Introduction 1:01 - 1:41
Starting With What We Know? 1:41 - 2:34
How Do We Transition To Level By Level? 2:34 - 2:41
Connecting Trees & Graphs (no pun intended) 2:41 - 3:04
Do You See A Graph Or A Tree? 3:04 - 3:53
Notice That This Is The Same Tree 3:53 - 5:07
Back To The Original Tree 5:07 - 5:50
We Realize Breadth First Search Is Most Natural 5:50 - 6:25
What Do We Use For Breadth First Search 6:25 - 7:22
Walking Through The Breadth First Search 7:22 - 11:22
The Breadth First Search Is Finished 11:22 - 12:03
Wrap Up 12:03 - 12:36

I Forgot Complexities -> Let n be the # of nodes in the binary tree. Time complexity is O(n) since we process n nodes and perform O(1) work per node processed. Space complexity is O(n) if we put all nodes in an array of arrays (each level gets its own array). Space is also O(n) if the output is not included since the upper bound on the number of items in the queue at any one moment in time will be a fractional component of n. The fractional constant disappears and yields O(n) space. Space scales in a linear fashion with the input size.

The code for this problem is in the description. Fully commented for teaching purposes.

[vasachisenjubean]

you are among the few people who keep DSA interesting

[ObsessedAwe]

May God bless this man beyond his wildest dreams.

[prithazz]

I feel like you are my BFF during interview prep. Otherwise, I would be crying by myself

[nedwilliams]

For me, it clicks. Recursion, BFS, Binary Structures. They're all just clicking thanks to you. Your style of working it out step by step is exactly what I do at home, I have a couple of white boards as well. But your way of looking at these problems has really solidified my understanding. Hats off, sir.

[yicai]

The GREATEST explanation about binary tree level order

[nurlanikhsanov]

Man, you are an amazing teacher! Please, keep going!

[amilaiddamalgoda]

One of the best explanations by far! keep it up 👍

[OllytheOzzy]

Dude you make it all so so so clear and easy to understand. Thankyou so much

[tannerbarcelos]

I have a interview at SAP next Wednesday. It’s for their new grad talent program. I applied and did an assessment for frontend, and got through that and the first interview. However now it’s technical. I’m not really sure if it’s gonna be related to frontend and such or just basic SWE interview stuff.

That said, for a new grad type of role, typically what should someone like me, interviewing for such a role AND never interviewing before, be focusing on?

Thank you so much brother. You explained this algorithm amazingly. I see tons of problems requiring BFS / Level Order stuff

[svdfxd]

As usual, great video. Like the way you explain things by a little revision of topics already learnt e.g. queues used for BFS, stacks used for DFS etc. Keep making these awesome videos to cover all the interview related topics/ questions.

[matthall]

Well done good sir!!! You drastically reduce the amount of time needed to study these problems!!!

[brandonelzy]

Really amazing explanation. Your tutorials are invaluable. I really appreciate this. Thank you.

[jingjing]

Thank you so much for this content. I like the way that you explain logic clearly. I appreciate your time to do this. Thanks Ben.

[KPsparks]

You do sucha great job explaining concepts!

[lsamparkl]

this is so insightful
other videos are just plainly teaching how the algorithm works.


I also like how you derived at that solution. Ideation is such an important skill to improve upon.
I feel like no one does that when explaining the solution.

[avery]

Your videos are amazing and so helpful! Please keep them coming!

[arinmis]

Just awesome. You tell those things too clear and it makes this perfect.

[danielzheng]

Very good video and easy understanding explanation. Thumb up!

[rakeshreddyabbireddy]

Your teaching is like, hey I don't teach coding but force your brain to code on your own after this lesson. Really you are brain friendly. I think in future you are going to make many new concepts on this channel