Binary Tree Level Order Traversal - BFS - Leetcode 102

0:00 - Read the problem

leetcode 102

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

[lovleenkaur]

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

[anjaliyadav]

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

[kockarthur]

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

[vinaf]

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

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

[colinrickels]

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.

[jonaskhanwald]

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.

[ThethProgrammer]

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.

[Daedalus]

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

[mehershrishtinigam]

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.

[viceroyop]

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.

[FizzaAhmad-upns]

Thank you man for so much better explanation.

[Sethsm]

Very clean and clear explanation, thanks!

[monicawang]

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

[davisward]

your code is so clean. thanks so much!

[shristyagarwal]

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

[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

[patrickfeeney]

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.