Binary Tree Level Order Traversal - BFS - Leetcode 102

🚀 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

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

[@anjaliyadav9360]

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

[@NeetCode]

Tree Playlist: czcams.com/video/OnSn2XEQ4MY/video.html

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

[@Sethsm1]

Very clean and clear explanation, thanks!

[@davisward3144]

your code is so clean. thanks so much!

[@akshaygupta8332]

Excellent explanation! Thanks a lot!!

[@MichaelShingo]

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

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

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

[@user-dc7oj3el7o]

such a clear explanation! Thank you 👍

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

[@Daedalus675]

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

[@CST1992]

Was

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

[@vandananayak9426]

Thank you for all the good work

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

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

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

[@expansivegymnast1020]

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

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

[@whonayem01]

Nice solution!

[@namanvohra8262]

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

[@kirillzlobin7135]

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

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

[@ilang747]

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

[@sarvarjuraev1376]

Thanks a lot for clear explanation

[@JohnnyMetz]

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

[@mikemihay]

Thank you !

[@sundararajannarasiman5613]

Nice video on BFS

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

[@pavelmaisiuk-dranko746]

Thanks for explanation)

[@johnpaul4301]

Thanks mate

[@hhcdghjjgsdrt235]

King of algo, my man

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

[@joshuamarcano350]

What are you using to do your blackboarding ?

[@majesticflyingbrick]

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

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

[@n.h.son1902]

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

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

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

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

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

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

[@nagendrabommireddi8437]

thank you sir

[@daniellim1212]

5:49 not a bst

[@pragyachauhan]

What whiteboard do you use for explanations?

[@NeetCode]

I use Paint3D

[@chair_smesh]

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

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

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

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

[@edwardteach2]

U a God

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

[@shalsteven]

You are so smart.

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

[@danielbzhang3280]

Please make a video about max Width Of Binary Tree please

[@goodhuman1]

Thanks a lot 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)

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

[@jaysonp9426]

I was with you until I saw how you name variables

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

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

[@shreehari2589]

Freaking genius 😘

[@samuel2318]

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

[@wecankinetic]

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

[@ketansharma6955]

noice

[@Goodday-nm7zp]

I love this channel!!

[@kirillzlobin7135]

You are the legend maaaan

[@aquapisces]

what if the node 9 also had children

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

[@buttofthejoke]

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?

[@rafaf8764]

LOVE U

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