Binary Tree Level Order Traversal - Drawing The Parallel Between Trees & Graphs
HTML-код
- Опубликовано: 2 окт 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 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).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech 
Наука
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.
I'm not finding the code in the description
ruclips.net/video/lw3Or6eqIpI/видео.html
Back To Back SWE lol
@@Azx499 Same
Where is the code? I can't find in the description
May God bless this man beyond his wildest dreams.
Dude you make it all so so so clear and easy to understand. Thankyou so much
ye
I feel like you are my BFF during interview prep. Otherwise, I would be crying by myself
sure if u want
I'm crying even with these videos. Can't do any tree/graph LC mediums.
People get friendzoned even when not asked lol
not seen the code in the description.
thank you for a great explanetion
hey man!
Firstly I would like to say that, I am a great admirer of ur work ...u r really doing something which matters a lot.
I would like to know that if there is any Email id where I can drop u the mails, actually my placements r coming ...it will be starting from July ...so I am kinda a nervous , I am watching ur videos daily and i am learning alot...i will really appreciate if u can guide me what to do..
and lastly...
Is this the pseudo code for the level order traversal is correct??
while(queue is NotNULL)
{
p =sizeof(queue);
while(p!=0)
{
print(front)
enqueue(front->left)
enqueue(front->right)
dequeue(front)
p--
}
}
thanks and I'm not sure there is much I can do to help with your placements. And there is code in the description
Thats an amazing video, it really helped me to understand BFS.
excellent
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.
Workin on it. I wish this could be my full-time job for a little. Too much work ahead.
you are among the few people who keep DSA interesting
thanks haha
fax
Really amazing explanation. Your tutorials are invaluable. I really appreciate this. Thank you.
thanks
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.
sure, we have a long way to go.
It seems like you removed the link to the code in the description?
A Great Teacher. Thanks a lot.
@Back To Back SWE -
Awesome video !! I have one question, you mentioned in the description that the space complexity without output is also o(n), 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).
My question is, will it always be slightly less than O(n) as never we will have all nodes stored in level and in queue? Could you please elaborate further
I want to read and reply but speed replying im sorry I love you
@@BackToBackSWE haha well I luv u 2 and waiting for ur reply :D
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
I don't think I'm well positioned to answer this, you should as others who interviewed (if you can get a hold of them)
you are awesome ty
One of the best explanations by far! keep it up 👍
ye
Where is the code for this, I couldn't find it in description.
We maintain the code on backtobackswe.com
My dude.. that was an amazing video. I appreciate you. Thanks.
ye
there is no code in the description
I don't ever find the code anymore, which makes it hard for me to write it myself even if I understand the explanation.
noted - we only maintain code on backtobackswe.com now
Boom. 256th like. On to the next byte of likes. I feel special 😄
nice
WHERE IS THE "CODE IN THE DESCRIPTION"? Looks like I'm never able to see it
The repository is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE I'd really appreciate if you give the codes to people who really need it for free. Great job explaining all the tough algos 🙏🏽
Dude should be paid $millions to teach Data Structures!! idk which college gonna discover this man first omg i Wish you were my professor haha
You do sucha great job explaining concepts!
sure
where's the code ?!
Hi, the code is maintained on www.backtobackswe.com
Well done good sir!!! You drastically reduce the amount of time needed to study these problems!!!
haha nice
where is the code?
The repository is deprecated - we only maintain backtobackswe.com now.
I feel like also adding and talking about code rather than just talking about algo would be helpful.
Hey first time viewer, so far I'm liking the content do you have a playlist that has the videos in like sequential order. like the concepts will build off the previous video. thanks
Hey.
I wish I did. I mean, I just do whatever questions I find immediately interesting or pull from a question list I have.
I have channel playlists but I ran out of those, I can't make anymore.
Back To Back SWE no problem 🤙🏾 I'll just watch all the concepts idk as well
First video with 0 disklies. Great
ye
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
lol, I am brain friendly lmao great
Thank you so much for this explanation.
sure
I imagine we feel the same way about "conclusions" lol
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.
thanks
You help alot Sir,THANKYOU SOO MUCH FOR THE VIDEOS.
sure
lol, thumbnail photo ! this was helpful, ty
my b - older me was whack
Such a great teacher!
thank you!
The GREATEST explanation about binary tree level order
thx
Is the code moved out from this description
uh, where's the code
The repository is deprecated and we only maintain backtobackswe.com now.
I did this exact same thing when I wanted to print out a visual representation of a BST. If i would have watched this video it would not have taken as long as it did figuring this out myself
Thank you!! great explanation!
Hey, I was wondering if you’re ever going to go back to the format of also explaining the code in the video kinda like the N Queens video? If not then it’s cool lol
Also I’m watching this video with earphones and I just wanted to give a heads up that for the audio you could hear a low echo and also a low static noice as well from some feedback the mic is picking up
Yeah, I don't think I am ever since I set the GitHub up. And also, yes I know about the static, I messed up the levels. I am still learning how to use the microphone.
For this video I didn't get the mic close enough to my mouth (it was mounted to the camera). I was lazy and didn't use my boom kit.
Check out today's video, I made the sound better I think.
Thank you for all your videos!!
Very good video and easy understanding explanation. Thumb up!
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.
Brooo you are the best I'll definitely help this channel after cracking my interview
There is no code in the description 8:09
Thank you for this, helped me visualize it
Man, you are an amazing teacher! Please, keep going!
holy shit this makes so much sense
These videos are awesome. It seems like knowing the patterns and having the toolsets to solve any kind of problem is important (as you always mention). When was the moment that you had the feeling that you had all these toolsets to apply to any kind of problem?
I still don't think I have "all [these] toolsets" but I guess it is when you immediately know what type of problem a problem is.
Noticing dynamic programming immediately. Noticing a BFS quickly. Knowing if the solution can be done with 2 pointers in O(n) time.
I'm really not THAT good...I'm ok...but yeah.
@@BackToBackSWE Nice. I am still struggling with many questions, but at least I know how to approach it. What is the next step after "Knowing which toolset to use"?
@@jkim5118 Just having done a lot of questions so that approaches come to mind. It is really all about experience. Intuitions can only go so far.
Your videos are amazing and so helpful! Please keep them coming!
Where is the code? I can't find in the description
You can check out the code repository on backtobackswe.com/
your videos are awesome. thank you :)
sure
where is the code man ?
You have a noble mission sir! thank you for the great video.
ye
Just awesome. You tell those things too clear and it makes this perfect.
Great work!
thanks
Great explanation
This man is amazing
You are simply awesome. You made it so simple
Amazing!
ye
i just wanna hug you .you are the best man
thank you
This man is an outstanding teacher.
awsome!
thanks
Awesome
You are great man♥️
thanks
this is awesome :D
thanks
dfds
Great video!
thanks
good job man
thanks
I neeeeed serious help with compiler, do you guys do that!!!!
haha I'm not a compiler expert