Binary Tree Level Order Traversal
HTML-код
- Опубликовано: 10 фев 2019
- For business inquiries email partnerships@k2.codes My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
DISCORD CHANNEL
----------------------------------------------------------------------------------------------------------------
To join the Discord channel use the following link and join the "Member" tier: / kevinnaughtonjr
In this Discord channel, you will be able to...
1. Ask me questions directly (as well as other members)
2. Ask about and discuss previous interview experiences
3. Find mock interview partners
4. Share helpful videos for interview preparation, and more!
This question is commonly asked by the following companies: Google, Facebook, Amazon, Uber, Microsoft, Oracle, Bloomberg, LinkedIn, and Walmart Labs.
Link to problem: leetcode.com/problems/binary-...
Intuition behind solution: Create a queue and add the root to the queue. While the queue is not empty process all the nodes in the queue. At every iteration of the queue not being empty, get the size of the queue (this represents however many nodes are on the current level of the tree). Iterate through all these nodes with a for loop, adding their values to a "current level" list. After adding their value to the list, check if they have left and right children adding them to the queue is they do exist (this allows us to process the next level of the tree on the next iteration of our while loop). Once our for loop terminates we have populated a list of all the nodes' values on the current level and we add this list to our return value (a list of lists). Once our while loop ends we have processed all the levels of the true and therefore return our result (our list of lists).
SOCIAL
----------------------------------------------------------------------------------------------------------------
Support me on Patreon: / kevinnaughtonjr
Follow me on Twitter: / kevinnaughtonjr
Follow me on Instagram: / kevinnaught. .
Follow me on GitHub: github.com/kdn251
MUSIC
----------------------------------------------------------------------------------------------------------------
Blushes by Dj Quads
/ blushes
rose & boujee by memori ("me over mori")
/ rose-and-boujee
#coding #interviews #softwareengineering Discord: bit.ly/K2-discord 
Наука
came for the BFS advice, stayed for the chill lofi migos remix
hahah great song...I hope you found the video helpful Jeremy!
I am glad I saw your link in the leetcode discussion. I need to practice more queue and stack "iterative recursive" algorithms.
So happy you saw the link too thanks for stopping by! Def practice them they're important!
Such a simple and genius explanation! Before this video BFS for me was harder than recursive DFS. Now I can understand both. Big thanks to you!
This is amazing. I struggled understanding BFS but this is the best explanation I have seen so far. Thank you so much!
always coming thru w a clear and concise explanation/approach.good looks bro keep it up!
Jairo Rubio thanks Jairo really appreciate that and don’t worry I will!
Awesome man! BFS within just 5 minutes with such clear explanation
Very helpful video, I was struggling with the explanation on leetcode. This video made it too easier to understand and that too in minimum amount of time. Thank you!
Anytime Alankar happy to hear the video was helpful! :)
Yoo I am so thankful for your channel, I am able to learn a lot thanks to your easy explanations! Thank you so much!!
That Walmart Labs gesture was hilarious though! Please upload some videos for Linked Lists as well.
You're very awesome. I always search for your videos first whenever I get stuck in a leetcode problem. Thanks a lot
Thanks! If you need help with these kinds of problems be sure to sign up for the interviewing service I created! thedailybyte.dev/?ref=kevin I recommend joining the annual tier if you can!
@Kevin Naughton Jr.
Before watching your video, I implemented a level-order traversal that was okay, but it put everything in just one list.
But after watching your video I realised that I don't have to use just one dequeue operation for each enqueue operation.
Like a lightning that struck me.
And for size of current level, I was using 2^n kind of logic. but your answer simplified it very much.
Thank you very much!!!
The "int size = queue.size()" was the trick and I was missing it :). Great
Awesome! This is what I was looking for.
Have been looking for the level-specific control over the BFS for a while. The trick found in this video is to iterate the level with the queue length.
This trick is also useful to find the level-average of a tree (another FB question on Leet) Thanks man!!! also watched the running gurlfriend behind you in other videos :-) lol..
* Level average
* Level minimum
* Level maximum
And everything that has to do with level.
So glad that I came across this video.
Hi Kevin , great job as usual ! just a suggestion, It would be better if a quick time/space complexity analysis is included at the end of the video! :)
Thank you thank you thank you. Such a simple and elegant solution!
Life Simply Rocks anytime! If you need help with more problems like this be sure to sign up for the interviewing service I made The Daily Byte. I recommend joining a premium plan if you can! thedailybyte.dev/?ref=kevin
Thank you, very much, i was stuck since it was hard to keep track of levels
Man! I love your videos. Super cool explanation. I would love it if the background music was a bit less loud if that is okay by you!
Thanks Darshan! And in more recent videos I think I'd toned down the volume more :)
Always found BFS and DFS difficult to understand. Loved your video and explanation. Thanks to your video I could understand better ! Could you please explain and code the recursive version as well ?
Short, easy, precise explanation. Thanks.
You are amazing dude. You explain it really quick and easy.
My man has exquisite music taste. I love it lol
You are right. I always found it difficult to understand BFS and wound never forget it now. Thanks
Harpreet Singh if you need help with other stuff interview related be sure to check out The Daily Byte! thedailybyte.dev/
You are gem 💎 Thank you so much!
Dope explanation :) Thank you so much man
Anytime I hope it was helpful! :)
Wow...so simple & superb explanation.
Anyone know what is the time complexity of this? Thanks in advance! :)
Hi, great video but what is the time and space complexity for this? Thank you!
you made it look so simple .... good work bro. thank you
You are my remedial Teacher :)
Very helpful video, thank you!
What is the time complexity for this?
hey kevin ! I don't know how to get comfortable with these recursion type of problems , I mean it never happened to me that I know how to apply recursion in the right way ...help me out plz
Hi Kevin, in the algo you described where the processing of queue is performed, you find out the size of queue and then looped all the result, on submission output is [[3],[9,20],[15,7]]. I instead of finding out the size used while loop till its not empty and i got result [[3,9,20,15,7]]. So didn't get why it happens like this. can you help!
Awesome dude!! solution looks clean and yet powerful. Is it possible to solve it using recursion?
If you use enhanced for loop. Will it cause an exception?
Dammn... this solution was great.
Thanks for the video bruh!
Amazing explanation you making our life easy... thanks Kevin :-)
so for every iteration, or every level in the tree, you will have the correct set of elements because you popped the previous level's nodes off of the queue?
Thanks bro.
Well explained.
Thank you!
Hey man, love your videos! Just a small request, the music makes it a bit hard to concentrate esp with the high pitches.. would really appreciate if the volume was lower. Thanks again
Is there a specific reason we use a LinkedList for the queue?
Edit: b/c constant time insertion and deletion
bcz we dont know the exact number of elements we are adding in the queue
You explain so well
Great explanation! Tysm. Please don't add background music while explaining. :)
can you do Binary Tree Level Order Traversal II.... which may be use stack implementation?
the music in all these vids is a meme
Thanks mate
Love you Kevin !
good job!!! Keep going
Thank you! Just checked out your channel looks like you're doing some great things keep up the good work!!! Happy to see we're both trying to help people!
You guys should do a collab together ! :)
@@satheshbm92 👀👀👀🤫🤫
what about the time complexity, any idea guys...?
Awesome video thanks man
Anytime!
Hi Kevin, can you please let me know why did you use Linkedlist here : Queue queue = new LinkedList(); , while ArrayList were used in other 2 places?
thanks~!!!!
Hey kevin you are awsome bro , keep it up
List abc=new ArrayList();
List abc=new ArrayList();
can we really assign the nested constructors?
Memory usage can be improved (better than 100% of java solutions) simply by replacing the LinkedList queue with an ArrayDeque Deque:
class Solution {
public List levelOrder(TreeNode root) {
List result = new ArrayList();
if (root == null)
return result;
Deque queue = new ArrayDeque();
queue.addLast(root);
while (queue.size() > 0) {
List currLevel = new ArrayList();
int currNumNodes = queue.size(); // number of nodes in the current level
for (int i = 0; i < currNumNodes; i++) {
TreeNode currNode = queue.removeFirst();
currLevel.add(currNode.val);
if (currNode.left != null) queue.addLast(currNode.left);
if (currNode.right != null) queue.addLast(currNode.right);
}
result.add(currLevel);
}
return result;
}
}
on 17 th line 2:05 why did you write queue and then linked list at the end. please explain
and also you Instagram link is not working
Hi Kevin...your explanation is really great...just for some questions it would be nice if u can explain through some diagrams or on paper too ...
Thanks kevin!
Anytime thanks for the support I really appreciate it!
This was very clear
Great solution,but I don't hear any explanation, at least not up to @5:06 of ~why~ the currentLevel contains the current-level-nodes. I did get it why.. but it wasn't said why
Thank you for this awesome video
Anytime I hope it was helpful!
but it's NOT !, you can do exactly the same without ever using a queue, just traverse the tree recursively, passing "depth" and a callback as a parameter, and add the values of the node to the result in the callback (an array of arrays, where the index is the depth), i don't see the need for a queue here at all
@@pizzagorgonzola Kevin's video is helpful. There are often multiple methods to solve one problem and it's a good idea to become familiar with different approaches. Each approach has its pros and cons, so try not to dismiss alternative solutions.
@@eileencrusta2448 you are wrong, while this is a long time ago, i think his method is slower, it allocates memory !, u don't need to allocate ANY memory to traverse a tree, this is a black and white issue, this is NOT the way to do this at all
@@pizzagorgonzola Yeah, I realized your original comment was from a year ago. Thanks for coming back to reply to me! (: I haven't written out the recursive algorithm as you described. However, when you're doing a level order traversal or breadth first search in a tree, I get the impression that using a queue is much more practical. A bit of memory savings isn't always the most important factor. Sometimes a solution that uses more memory makes more sense practically.
If the problem wasn't specifically to return an array of values level by level, then I believe a recursive approach would make more sense. Thanks again for your input.
Thanks
CULTURE III is coming hahaha
Btw, thanks for the vid!
Yi Cai anytime and DUDEEEEE can’t wait for that to drop
can you please explain 1130. Minimum Cost Tree From Leaf Values
Better than the explanation on leetcode
thanks!
i can see you have submitted multiple time and got some error . if you can discuss those error then it would be really helpful for us.
lol, nice music choice... 😅
Thanks for the video.
Can you also upload the background music free version of the same video?
Anytime! Unfortunately, I don't think I'm going to upload the same video without audio but maybe you can try watching with no sound and put on the captions? Sorry about the music, I'm still trying to decide if I should include it in the videos or not (I feel like some people might get bored just hearing my voice?). If I do decide to use music I'll try to make sure it's pretty quiet and not distracting, sorry if it bothered you!
@@KevinNaughtonJr It's ok. No problem at all. Just don't stop making videos.
@@rajivranjan6268 Don't worry I won't and thanks for understanding!
thank you king
What do you think of this:
var levelOrder = function(root) {
let result = [];
let level = 1;
function traversal(node) { //3;
if (node === null) {
return;
}
if (result[level - 1] === undefined) {
result[level - 1] = [];
}
result[level - 1].push(node.val);
level++ //2;
traversal(node.left);
traversal(node.right);
level--;
}
traversal(root);
return result;
};
The idea is just to keep level and push each node value to the specific array index, which is level - 1.
I'm a bit confused here. Why did you add currentLevel to the result, but in lines 26 and 29 you're adding the values to the queue. Are the queue and currentLevel list holding the same values? Hope you can clarify.
que here is to track all elements which are at same level so at each iteration queue will contain only same level elements
and current level will contain all those elements
queue as Linked list ?!! why how where when
You made it simple. Thanks for explaining bfs algorithm.
can you also explain 23 line 3:58
this would be easier to understand if you went through an example before going into code.
Python solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
#Iterative solution using BFS. Remember, we use Queue in BFS
# We are using Queue here.
if root == None:
return []
result = []
queue = []
#append root
queue.append(root)
# do while queue is empty
while (queue):
#size represent total nodes at that level
size = len(queue)
#set currentlevel to store elements of a level, reset again after for loop ends for every level
currentlevel = []
#for all nodes at a level, pop a node and append it to currentlevel
for i in range(size):
current = queue.pop(0)
currentlevel.append(current.val)
#if node has left child, add it to queue
if current.left:
queue.append(current.left)
#if node has right child, add it to queue
if current.right:
queue.append(current.right)
#after for loop ends, append all nodes in currentlevel to our result
result.append(list(currentlevel))
#return result
return result
I wish it was in c++ :(
Do you know why you got a compile error? I feel that this is important to mention in an interview.
Hey Neal! That was actually on a separate submission previous to the video. If I remember correctly it was a small syntax error like forgetting a semicolon
who else feels the music helped to understand the solution better
azeez taiwo I agree :)
Helpful but music is so annoying
do you need a queue for this ? no
Rather than writing code directly you could have explained concept on white board first and then code and also brute- > optimised approach is better...Otherwise its useless..