Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python

0:00 - Read the problem
1:28 - Recursive DFS
5:30 - BFS Solution
10:43 - Iterative DFS

leetcode 104

#binary #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[A]

this was really good, thanks foe showing us the different ways to solve the same problem because its like learning more than one thing at the same time (BFS, DFS, recursion, binary tree traversal, queues, stacks, etc. all in one video)

[kleadfusha]

Your explanations have always been pretty amazing, but somehow they keep getting better and better!!

[deewademai]

The third solution should replace the order of "left" and "right" of the stack.append to become a pre-order tree traversal.

[iknoorsingh]

Hi Neetcode, Great work, keep it up!
In iterative dfs, I think you should append the right node first because then it should be preorder traversal. But both will work the same anyway.

[jasonswift]

This is an extremely wonderful explanation. Keep up the hard work. Btw, it is the post-order method for drawing the third solution. The code of the third solution is a pre-order method. Anyway, It doesn't matter the result of this question. We can take either of pre-order method or the post-order method.

[tonyz]

for the DFS iterative, why do we need to add the Null Node to the stack? We can do :
if node.left:
stack.append([node.left, depth+1])
if node.right:
stack.append([node.right, depth+1])

[lonecreeperbrine]

IDK if this changes anything and if it doesn't can someone explain why. In the last solution when you added things to the stack you appended node.left and then node.right but for preorder traversal shouldn't have node.right been appended then node.left so when you pop the stack the left node is popped first ?

[michaelyao]

Somehow, I feel like the iterative dfs is not so `dfs`, it's till kind of `bfs`.

[KarthikChintalaOfficial]

Hey NeetCode,

In the Iterative DFS approach, within the while loop, if we append like this

stack.append(node.left, depth+1);
stack.append(node.right, depth+1);


When we pop in the next iteration, then the right child will be popped and their children will be added right (because the right child is added last in the stack). I think the order should be reversed here so that the left children will be popped in the next iteration

[marcoespinoza]

God bless you. I have stumbled on your channel and it has been helping me a lot with your explanations. I like how you did all three ways of doing this to help build that intuition for all of them. Thank you so much for making these videos.

[abh]

How do you create these videos like on iPad or on the computer as its difficult to drawing otherwise ?

[OMFGallusernamesgone]

for BFS, couldnt we just use your iterative DFS solution, but replace the stack with a queue?

[hemesh]

Hey as we are following pre order, the order shd be root, left, right then as stack follow lifo shdnt we insert right first and left, this is small doubt anyway technically we will get same. sorry for asking a lame doubt please excuse me.

[syafzal]

I had only coded up the recursive way, but good to know about the other 2 ways you described in this video

[dipakkumarrai]

Thank you so much for the diagrams sketch! It became clear now

[adventurer]

Excellent diverse approaches! The code explanation of the last one was pretty confusing though.

[avtarchandra]

5:11 made me laugh @neetcode...."I am showing that I am not able to solve even easy problem"

[riturajsingh]

Can you explain why we used 'self', even when we were in the same function (a reference to recursive solution line#12)

[theFifthMountain]

BFS is useful for Leetcode 111.Minimum Depth of Binary Tree. Once you find the first leaf node, (not cur.left and not cur.right) return 1 + depth

[szu-minyu]

Thank you for the clear explanation! You are wonderful :)