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.
@@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
"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()"
@@seenumadhavan4451 yes but that way the time would be O(n) as if you remove from the first index it will shift all the other elements by one position! That's why we use the deque data structure to do that in O(1) time.
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.
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.
There is a need. It is for last nodes in q. There will be [None,None,None,None] . It is True in Python. That is why last run will add empty list to res
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 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.
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.
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.
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)
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.
Wow, was really simple to figure this out alone after that task of calculating the height of the tree you solved via DFS (iterative and recursive) and BFS
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.
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
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 :)
A little advice🙏 If you make an animation part at the last of the video where you debug the code with animation to show why and how this code and every iteration work.
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.
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.😅
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
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
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?
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())
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).
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)
@@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)
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)
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!!!
i think this problem is actually closer to easy than medium
stop acting so cocky. The guy is happy because he could solve the problem and you go "WeLl aKshUallY tHat's aN EaSY prOblEm 🤓☝️" @@2NormalHuman
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 :)
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.
I usually see your solutions after trying out myself. Almost always get a new way to solve. Keep it up!
ooo I got the BFS part but really the key to the problem is to know when each level ends thanks
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 :)
"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 😊
@@seenumadhavan4451 yes but that way the time would be O(n) as if you remove from the first index it will shift all the other elements by one position!
That's why we use the deque data structure to do that in O(1) time.
Def the best coding channel on yt. There's a reason why he's at Google.
Was
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
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.
There is a need. It is for last nodes in q. There will be [None,None,None,None] . It is True in Python. That is why last run will add empty list to res
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 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.
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.
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
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.
Wow, was really simple to figure this out alone after that task of calculating the height of the tree you solved via DFS (iterative and recursive) and BFS
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.
Very clean and clear explanation, thanks!
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
your code is so clean. thanks so much!
Thank you man for so much better explanation.
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 :)
A little advice🙏
If you make an animation part at the last of the video where you debug the code with animation to show why and how this code and every iteration work.
Any reason why you're using collections.deque() instead of queue.Queue() ? Is one faster than the other?
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?
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.
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.😅
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
Good explanation. I solved number of islands, and 01 Matrix and then got stuck on this problem.
such a clear explanation! Thank you 👍
7:45 I wonder why you said it is possible for the node could be null?
5:49 not a bst
Excellent explanation! Thanks a lot!!
Thank you for all the good work
You are super talented to explain such complex stuff in a soo easy-to-understand way... This is amazing
Thanks a lot man ❤
What are you using to do your blackboarding ?
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)
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.
why time complexity is O(n)? shouldn't it be O(n+e) since we're running bfs?
Nice video as usual! But why did u add another condition of if Level?
In your explanation you did not add null nodes into the queue, but in your code you did.
Thanks a lot for clear explanation
very nice explaination, thanks
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)
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:
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())
same
What whiteboard do you use for explanations?
I use Paint3D
@@NeetCode Did google let you use Paint3D for remote interviews?
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
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
Nice solution!
I was with you until I saw how you name variables
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).
Nah since you're just only visiting each node and not performing any operations depending on the height of the tree
Nice video on BFS
Thank you !
Thanks for explanation)
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)
King of algo, my man
Thanks mate
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
thank you sir
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
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
would love if these videos did more to explain how to come up with the solution instead of just describing the solution
You are so smart.
U a God
clear explanation! I solve it by myself, but I still come to see any alternative to solve this question.
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
I love this channel!!
Please make a video about max Width Of Binary Tree please
Freaking genius 😘
You are the legend maaaan
what if the node 9 also had children
who even invented binary trees bruh
noice
LOVE U
Only difference is you need to reverse the list so you might need to add res[: : -1] instead of just returning res
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