Binary Tree Level Order Traversal - BFS - Leetcode 102

[@Asdelatech]

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!!!

[@lovleenkaur1042]

Please make more such videos! Your explanation is super easy to be grasped. Thanks a lot for putting on the effort

[@NeetCode]

Thank you, I will :)

[@kockarthur7976]

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.

[@MichaelShingo]

ooo I got the BFS part but really the key to the problem is to know when each level ends thanks

[@vinaf4494]

"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]

You can pass list.pop(index) This will work for sure 😊

[@anubhav4636]

@@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.

[@The6thProgrammer]

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.

[@Flekks]

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

[@anjaliyadav9360]

I usually see your solutions after trying out myself. Almost always get a new way to solve. Keep it up!

[@jonaskhanwald566]

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.

[@colinrickels201]

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.

[@yinglll7411]

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.

[@minciNashu]

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.

[@nasdas123]

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

[@mehershrishtinigam5449]

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.

[@introspectiveengineer392]

I call dequeue "double ended queue" and deque "deck" to avoid confusion

[@viceroyop6385]

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.

[@draugno7]

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

[@WaldoTheWombat]

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

[@shristyagarwal3812]

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

[@Daedalus675]

Def the best coding channel on yt. There's a reason why he's at Google.

[@CST1992]

Was

[@monicawang8447]

i have a dumb question: why does the length of queue not change even though we append the left and right child nodes?

[@NeetCode]

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.

[@cgqqqq]

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)

[@rishabhnegi9806]

well it is changing as a matter of fact, it's just we are not using the updated queue size

[@souravbanerjee6457]

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.

[@AbhishekSingh-rs6tx]

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)

[@patrickfeeney4180]

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.

[@expansivegymnast1020]

Good explanation. I solved number of islands, and 01 Matrix and then got stuck on this problem.

[@jugsma6676]

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())

[@AlexA00]

same

[@FizzaAhmad-up8ns]

Thank you man for so much better explanation.

[@JohnnyMetz]

Any reason why you're using collections.deque() instead of queue.Queue() ? Is one faster than the other?

[@pengyan1906]

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)

[@majesticflyingbrick]

In your explanation you did not add null nodes into the queue, but in your code you did.

[@lemonke8132]

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

[@noorafifi9]

why time complexity is O(n)? shouldn't it be O(n+e) since we're running bfs?

[@daniellim1212]

5:49 not a bst

[@jeffjames15]

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.😅

[@VirtualKnowledgeHub]

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.

[@arina1193]

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

[@jackpott1322]

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?

[@jaysonp9426]

I was with you until I saw how you name variables

[@limingwei2636]

very nice explaination, thanks

[@n.h.son1902]

7:45 I wonder why you said it is possible for the node could be null?

[@Sethsm1]

Very clean and clear explanation, thanks!

[@sarvarjuraev1376]

Thanks a lot for clear explanation

[@davisward3144]

your code is so clean. thanks so much!

[@jvarunbharathi9013]

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).

[@jonathanc8734]

Nah since you're just only visiting each node and not performing any operations depending on the height of the tree

[@saumyaverma9581]

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?

[@varunshrivastava2706]

Instead of writing queue != None write if len(queue) > 0:

[@laveshchanchawat6983]

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?

[@rishabhnegi9806]

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

[@laveshchanchawat6983]

@@rishabhnegi9806 thank you bhai,par Hindi mai bata dete😅.jyada samaz ni aya.

[@kirillzlobin7135]

You are super talented to explain such complex stuff in a soo easy-to-understand way... This is amazing

[@wecankinetic]

would love if these videos did more to explain how to come up with the solution instead of just describing the solution

[@joshuamarcano350]

What are you using to do your blackboarding ?

[@andregabriel5246]

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 :)

[@송예은-h7b]

such a clear explanation! Thank you 👍

[@noumaaaan]

Are we allowed to use libraries like collections in coding interviews? Someone please let me know!

[@NeetCode]

Most of the time yes, unless the question specifically wants you to implement the underlying Data structure or algorithm

[@goodhuman1]

Thanks a lot man ❤

[@samuel2318]

clear explanation! I solve it by myself, but I still come to see any alternative to solve this question.

[@namanvohra8262]

Nice video as usual! But why did u add another condition of if Level?

[@akshaygupta8332]

Excellent explanation! Thanks a lot!!

[@vandananayak9426]

Thank you for all the good work

[@sundararajannarasiman5613]

Nice video on BFS

[@hhcdghjjgsdrt235]

King of algo, my man

[@keremserttas5898]

Hi, how can I implement the same solution using depth first search

[@keremserttas5898]

found my solution res = [] #DFS Solution def dfs(head,level): if head == None: return if len(res)

[@danielbzhang3280]

Please make a video about max Width Of Binary Tree please

[@whonayem01]

Nice solution!

[@pavelmaisiuk-dranko746]

Thanks for explanation)

[@pragyachauhan]

What whiteboard do you use for explanations?

[@NeetCode]

I use Paint3D

[@chair_smesh]

@@NeetCode Did google let you use Paint3D for remote interviews?

[@nagendrabommireddi8437]

thank you sir

[@mikemihay]

Thank you !

[@director8656]

is there a recursive solution to this problem, great video as usual!

[@saadwaraich1994]

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()

[@director8656]

@@saadwaraich1994 thanks a ton!

[@roderickdunn2517]

@@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.

[@erik-sandberg]

@@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

[@johnpaul4301]

Thanks mate

[@shalsteven]

You are so smart.

[@taran7649]

Can we use DFS TOO …?

[@supriyamanna715]

No buddy. BSF is level wise search. DFS goes to the depth

[@BlakeTB]

@@supriyamanna715 I believe someone else commented a dfs solution but it’s not as intuitive

[@edwardteach2]

U a God

[@Goodday-nm7zp]

I love this channel!!

[@kirillzlobin7135]

You are the legend maaaan

[@sumeetbisen9708]

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)

[@lordsixth5944]

Yoo buddy how old are you

[@aquapisces]

what if the node 9 also had children

[@shreehari2589]

Freaking genius 😘

[@ketansharma6955]

noice

[@rafaf8764]

LOVE U

[@NeetCode]

Tree Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@varunshrivastava2706]

Hey can you tell me for this question why did we wrote q.append(root) instead of q.append(root.val)?

[@lordsixth5944]

@@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

[@taymurnaeem50]

@@varunshrivastava2706 Because we need entire root node, along with its all children and grandchildren and so on.. Not just root node value.

[@varunshrivastava2706]

@@taymurnaeem50 yeah now I know that, god I was really dumb a year ago😂😂😂

[@servantofthelord8147]

@@varunshrivastava2706 You weren't dumb, you were just getting started :)

[@eddiej204]

[@user-oc6ky2tk5o]

had to add if level: res.append(level) for it to work on leetcode, not sure why this difference occured

[@minciNashu]

works without, for me

[@sanooosai]

thank you sir