Binary Tree Level Order Traversal - BFS - Leetcode 102
HTML-код
- Опубликовано: 2 мар 2021
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/level-or...
0:00 - Read the problem
leetcode 102
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#sorted #array #python 
Наука
Please make more such videos! Your explanation is super easy to be grasped. Thanks a lot for putting on the effort
Thank you, I will :)
I usually see your solutions after trying out myself. Almost always get a new way to solve. Keep it up!
This is the first time I was able to solve a tree-based leetcode medium problem on my own. Clearly, I am making progress every day. Thank you, man!!!
It is actually totally fine to do Depth First Search for this problem, because it is not necessary that we actually TRAVERSE the list level-by-level, despite the problem name "Level Order Traversal". We only need to output the list of node lists organized by level and ordered left-to-right.
Very clean and clear explanation, thanks!
your code is so clean. thanks so much!
Excellent explanation! Thanks a lot!!
such a clear explanation! Thank you 👍
ooo I got the BFS part but really the key to the problem is to know when each level ends thanks
Def the best coding channel on yt. There's a reason why he's at Google.
Was
Thank you for all the good work
"The pop() method is used to remove and return the right most element from the queue, and popleft() method is used to remove and return left most element from the queue."
Just a note to explain line 18, the ".popleft()"
You can pass list.pop(index)
This will work for sure 😊
First time I'm hearing someone call deque as "deck" and honestly that makes so much sense. Otherwise most people I know pronounce dequeue and deque the same, which can be confusing.
I call dequeue "double ended queue" and deque "deck" to avoid confusion
Now this solution is:
Runtime: 20 ms, faster than 99.87% of Python3 online submissions for Binary Tree Level Order Traversal.
Memory Usage: 14.3 MB, less than 96.23% of Python3 online submissions for Binary Tree Level Order Traversal.
I solved this using list as a stack with Python, since it's a stack and not a queue you would want to append the right child of each node before the left child so when you pop, you pop left child first for the correct ordering.
i have a dumb question: why does the length of queue not change even though we append the left and right child nodes?
That's a good question, it use to confuse me as well.
Think of it in terms of passing a value (in this case the queue length) into a function.
Basically, the for loop's range() is a function, and we are only calculating the length of the queue a single time and passing it into the range() function.
queue的长度一直是在改变的，每个while循环都会pop掉当前level所有的node，但是会在后面加上children的node信息 (虽然有些node是none)，但是由于规定了for i in range(len(q))，在你的queue接触到children的node信息之前，本次循环就已经终止了。所以queue在每个while循环都是更新元素的。你在while后面加入print就能看的很清楚：
while q:
print(len(q)) # print number of elements in queue in the beginning of this iteration
print(q)
well it is changing as a matter of fact, it's just we are not using the updated queue size
think of it like after passing the length of the queue to range() function, it converts it into a for loop of 0 to 4( say ), so here we don't have anything to do with the increasing queue size anymore but have to deal with it again when the loop initializes, you can also try it using forEach it also does the same thing.
I think it’s worth noting that with a binary tree, it’s more ideal to recursively feed the next left node through before moving on the right as a means of BFS. Given that this is the algo for any n tree though, I’m also seeing the benefit of prioritizing this approach.
hi @colinrickels201 I think what you are proposing is a DFS rather than BFS, which will make it difficult to keep track of which level of the tree you are currently in and preserve the order of nodes across each level.
you can do range(len(q)) safely. the range wont change dinamically.
also, i think it's better to check left and right for none before appending, this way you dont add null nodes to queue.
agreed, here-s my solution:
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
resList = []
q = collections.deque()
if root:
q.append(root)
while q:
level = []
qLen = len(q)
for node in range(qLen):
cur = q.popleft()
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
level.append(cur.val)
resList.append(level)
return resList
Any reason why you're using collections.deque() instead of queue.Queue() ? Is one faster than the other?
Hi,
How Leetcode executes program with default tree definition and other default definations?
I mean on local machine we define Tree class & initiate it's instance then we call the method with instance name & arguments.
Here, w/o creating instance & w/o providing values how does it work?
How to run this code on local machine without full code.
Please guide me on this.
Checking how many loops to do before you start the for-loop and then just looping that amount of times without looking at the queue at all as the condition for the loop is just so smart ffs. Fair play.
Thanks a lot for clear explanation
What are you using to do your blackboarding ?
Nice solution!
Nice video as usual! But why did u add another condition of if Level?
There is no need to check if level is empty before appending it to the result. The only way our while loop iterates is if the q contains >= 1 nodes. Therefore you are always appending at least a single node to the level list.
Nice video on BFS
Good explanation. I solved number of islands, and 01 Matrix and then got stuck on this problem.
Thank you !
When i use list instead of deque in this problem i get two times better processing time. it looks like list sometimes is more efficient than deque?
Thanks for explanation)
Thanks mate
King of algo, my man
You are super talented to explain such complex stuff in a soo easy-to-understand way... This is amazing
In your explanation you did not add null nodes into the queue, but in your code you did.
7:45 I wonder why you said it is possible for the node could be null?
Tree Playlist: ruclips.net/video/OnSn2XEQ4MY/видео.html
Hey can you tell me for this question why did we wrote q.append(root) instead of q.append(root.val)?
@@varunshrivastava2706 it has been three month but still
We are appending root not root.val cause after appending we have to iterate over it to get it's childrens hope it helps
@@varunshrivastava2706 Because we need entire root node, along with its all children and grandchildren and so on.. Not just root node value.
@@taymurnaeem50 yeah now I know that, god I was really dumb a year ago😂😂😂
@@varunshrivastava2706 You weren't dumb, you were just getting started :)
What whiteboard do you use for explanations?
I use Paint3D
@@NeetCode Did google let you use Paint3D for remote interviews?
int size = queue.size(); if we remove this line and directly use for(int i = 0; i < queue.size(); i++) why the output are different?
Maybe it's bcz your queue size is increasing with each loop because of the push operations of the child nodes instead it should have been constant { i.e. loop should have run only up to the previous size of the queue before pushing nodes left, right child nodes into it} … we are doing so because here as u can see we have to create list for every level and return a list with each level s its sub-list …in order to achieve that we are only running the loop till the size of every level ....but in your case instead of using the initial queue size as loop's limit your loop is running up to updated queue size which not only contains the node of the level but also some of their children's as well
@@rishabhnegi9806 thank you bhai,par Hindi mai bata dete😅.jyada samaz ni aya.
The idea is the same. The way I solved it feels more intuitive-
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if not root:
return ans
bQ = [(root, 0)]
prevL = -1
while bQ:
n, level = bQ.pop(0)
if prevL != level:
ans.append(n.val)
prevL = level
if n.right:
bQ.append((n.right, level + 1))
if n.left:
bQ.append((n.left, level + 1))
return ans
In the while condition if I say "while queue != None"" it was giving me "memory limit exceeded" not when I put "while queue:" it's accepted but what's the difference?
Instead of writing queue != None write if len(queue) > 0:
Are we allowed to use libraries like collections in coding interviews? Someone please let me know!
Most of the time yes, unless the question specifically wants you to implement the underlying Data structure or algorithm
Hi, how can I implement the same solution using depth first search
found my solution
res = []
#DFS Solution
def dfs(head,level):
if head == None:
return
if len(res)
thank you sir
Shouln't the time complexity be O(logn*n) because the forloop can run n/2 times at most and while loop runs log(n)(no of levels in tree) so isn't supposed to be O(n*logn).
Hey, great explanation! Just a correction for what was mentioned at 6:17 : the biggest level can have at most (n+1)/2 nodes, and not n/2. This leads also to O(n) space complexity, so it does not make the final analysis wrong :)
In the deque, I firstly thought if the left most element is popped, the index 0 will be automatically assigned to the second element, then the for loop will make no sense. It was just my misconception in my imagination, don’t know why I thought like that.😅
Thanks a lot man ❤
5:49 not a bst
You are so smart.
is there a recursive solution to this problem, great video as usual!
levels = collections.defaultdict(list)
def dfs(node, level):
if not node:
return
levels[str(level)].append(node.val)
dfs(node.left, level+1)
dfs(node.right, level+1)
dfs(root, 0)
return levels.values()
@@saadwaraich1994 thanks a ton!
@@saadwaraich1994 I don't think there's any need to use a dictionary or collection. Your 'levels' var could just be a plain list, with each index representing the corresponding level. Guess the only caveat is you have to check whether to append another sub-array on each iteration.
@@roderickdunn2517
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
# Depth first search
# At each depth, append value to that element in the array
def dfs(node, depth):
if not node:
return
if len(levels) == depth:
levels.append([])
levels[depth].append(node.val)
dfs(node.left, depth+1)
dfs(node.right, depth+1)
dfs(root, 0)
return levels
U a God
I used dfs, with cache:
def solution(root):
cache = {}
return helper(root, cache, 1)
def helper(root, cache, l):
if not root:
return []
if l not in cache:
cache[l] = [root.val]
else:
cache[l].append(root.val)
helper(root.left, cache, l+1)
helper(root.right, cache, l + 1)
return list(cache.values())
Using queue:
def levelOrder(self,root):
if root is None:
return
q = deque()
q.append(root)
while (len(q)>0):
root = q.popleft()
print(root.val,end=" ")
if(root.left is not None):
q.append(root.left)
if(root.right is not None):
q.append(root.right)
My version (checking if the children are not None instead of checking the node itself):
if root is None:
return []
q = deque()
q.append(root)
levels_vals = []
while q:
level_length = len(q)
values = []
for current_level_nodes_count in range(level_length):
node = q.popleft()
values.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
levels_vals.append(values)
return levels_vals
My dfs solution:
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
results = []
def preOrder(node, level):
if not node:
return
if level == len(results):
results.append([node.val])
else:
results[level].append(node.val)
preOrder(node.left, level + 1)
preOrder(node.right, level + 1)
preOrder(root, 0)
return results
Can we use DFS TOO …?
No buddy. BSF is level wise search. DFS goes to the depth
@@supriyamanna715 I believe someone else commented a dfs solution but it’s not as intuitive
Please make a video about max Width Of Binary Tree please
Instead of adding level.append(node.val), can't we directly push it into the result.append(node.val)? since we're already pushing it in that order?
line 21-22, if node.left/right do not exist, will q not append None? I did the following way:
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
q = deque([(root, 0)])
res = []
while q:
node, level = q.popleft()
if not node: continue
if level == len(res): res.append([])
res[level].append(node.val)
q.append((node.left, level + 1))
q.append((node.right, level + 1))
return res
noice
would love if these videos did more to explain how to come up with the solution instead of just describing the solution
I was with you until I saw how you name variables
Freaking genius 😘
I love this channel!!
clear explanation! I solve it by myself, but I still come to see any alternative to solve this question.
You are the legend maaaan
What will be the time complexity if I use recursion for this problem?
like this:
res = [ ]
def bfs(node, level):
if not node:
return
res[level].append(node.val)
bfs(node.left, level+1)
bfs(node.right, level+1)
Yoo buddy how old are you
what if the node 9 also had children
LOVE U
had to add
if level:
res.append(level)
for it to work on leetcode, not sure why this difference occured
works without, for me
thank you sir