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

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@534A53]

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)

[@kleadfusha8338]

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

[@NeetCode]

Thanks, I appreciate your kind words more than you think! 😃

[@deewademai]

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

[@jasonswift7468]

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.

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

[@ashok2089]

The results will be the same in either way.

[@iknoorsingh7454]

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.

[@ziyuzhao2442]

Yeah Thats correct

[@tonyz2203]

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

[@harishankar1368]

We can also choose to not do that and still the result will be the same.

[@vishnukumar4531]

additional if-checks as part of the code, that is all!

[@theFifthMountain123]

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

[@OMFGallusernamesgone]

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

[@divyashukla4321]

Great explanation, thank you. I do have 1 doubt - shouldn't time complexity for bfs in your solution be o(n*n) as in order of n square. Because first we are using while loop, then it has inner for loop. Hence to use two loops meaning inner loop shouldn't it be time complexity be order of n square ?

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

[@giancarlokuosmanen9723]

Neetcode simplifying leetcode, cheers man!

[@nikhilgoyal007]

thanks! right should have been appended before the left yes ?

[@syafzal273]

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

[@hemesh5663]

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.

[@michaelyao9389]

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

[@sirmidor]

What makes it DFS is that new nodes to search are appended on the right, which is the same place where nodes are popped from. This means that deeper nodes of depth X + 1, which were found from a previous node at depth X, will always be tried before potential other nodes of depth X.

[@adventurer2395]

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

[@BruhhMoment-ij5uo]

Hey, Can you tell me why are the leaf nodes returning 1 ? I think they should return 0 because their height is 0, so the height of the tree should be 2 right? because the no. of edges will be the height right?

[@marcoespinoza3327]

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.

[@dipakkumarrai1442]

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

[@abh830]

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

[@jugsma6676]

Another variant is: def solution(root): cache = {} return helper(root, cache, 1) def helper(root, cache, level): if not root: return True cache[level] = root.val # [root.val] helper(root.left, cache, level+1) helper(root.right, cache, level+1) return max(cache.keys())

[@riturajsingh9744]

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

[@NeetCode]

It's required in python, since the function belongs to the object (self)

[@avtarchandra2407]

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

[@draugno7]

How is the first soluton's memory complexity same as the other two's when we don't use additional data structure (deque or stack)?

[@raviyadav2552]

thnx for showing the different approaches

[@grigorypiskunov418]

Thank you Sir for your work, hardly appreciate that. I actually have a question about the 2nd implementation. If we user pop instead of popleft or use stack as list of values we have an issue for asymmetric trees. In this case we always have +1 vaules of levels. I have checked it with debugger and I don't understand yet why in case we append to the list it add instead of list to the upper Tree element a new one..

[@suri4Musiq]

Do we really need the for loop inside the iterative bfs algorithm? Esp when this is a binary tree?

[@kirillzlobin7135]

Wooow... almost one line solution ))) You are amazing!!!

[@knockknockyoo5812]

I've watched his videos for a while. This is one of the best lectures. Thank you so much.

[@suri4Musiq]

10:53 Isn't the recurisve DFS a post-order traversal? We first do left, then right and then the current node right? Atleast that's how your code looked in the first solution

[@haha-hs7yf]

What's the diffference between bfs and iterative dfs?

[@alexandersiewert9133]

I’m a bit confused on the DSF on why it would be max(result, depth) wouldn’t depth be good enough?

[@RC-qr8bn]

On the Iterative DFS explanation if its using preorder wouldn't 9 on the left subtree be added first to the stack and then 20? It looks like 20 was added first and then 9.

[@timswen5280]

I have the same question

[@TharaMesseroux1]

Thank you NeetCode for this series!

[@SARDARIN]

@ 11:25 you said in pre order traversal, we visit left tree first. That's not pre order, In preorder we visit the root node first, then the left and right trees.

[@Shivi1003]

Your videos are really very informative and helps a lot while solving questions .💙💙

[@BruhhMoment-ij5uo]

Hey, Can you tell me why are the leaf nodes returning 1 ? I think they should return 0 because their height is 0, so the height should be 2 right?

[@EdenObengNanaKyei]

In a binary tree, the node value on the right should always be greater than the node values on its left, and also the parent node. Does this make the example given by leetcode wrong?

[@srisai-j4k]

The explanation is very good. Please let me know where I can get this code. Please share the link

[@JSarko_]

Looking at the recursive dfs solution, how does traversing through each node return the value of 1 just by calling the function? so for example in the return line at 5:10, how does self.maxDepth(node.left) generate a value to be compared with in the max function? I don't see how it gets incremented with every function call? Just like to add the explanation of the algorithm is great, its just from a coding standpoint I don't understand because self.maxDepth(node.left) by itself returns 0

[@jesalgandhi]

I am also confused about this, if anyone can provide a clear explanation of how a node generates a return value when recursing that would be very helpful

[@natnaelberhane3141]

That's because we're adding 1 for each level. So for example, in the recursion, if the tree is empty, we return 0. That would terminate our code and return 0. But if our tree has at least a root, then the depth becomes 1. so we add that value for each level we encounter. that's why the recursive code is return 1 + max(maxDepth(root.left), maxDepth(root.right). So this means, as we go deeper into the tree, we keep adding 1 for each root or level. But once we reach the leaf nodes, the root.left and root.right of the leaf node would return 0. For example, if we have a tree with 3 levels, a b c d e our function call would be 1 + max(maxDepth(b), maxDepth(c)). maxDepth(b) would be 1 + maxDepth(d) maxDepth of d would be 1 + max(maxDepth(d.left, d.right)) both d.left and d.right are none (we hit our base case). Therefore they both return 0. This means maxDepth(d) would be 1 + 0 maxDepth(b) == 1 + maxDepth(d) which is 1 + 1 maxDepth(a) would be 1 + maxDepth(b) which is 1 + 1 + 1 So the function will finally return 3. Btw since the tree is symmetrical, I only took the a->b->d part of the tree for this explanation.

[@namoan1216]

At first it is confusing for me but then I realized and your ideas are really effective

[@darrylbrian]

@neetcode - heads up, the link to this video on your website actually takes you to the comments page instead of the video itself.

[@taran7649]

The BFS and DFS are both iterative right

[@RandomShowerThoughts]

you might be the best at explaining these types of problems, and the theory behind them, wow

[@peanutbutter785]

Such a clear explanation! Thank you :)

[@RC-qr8bn]

Do you think if I solved this question in a real interview with just recursive DFS would that be enough or should I also learn the iterative way to solve it too just in case.

[@legatusmaximus6275]

Know iterative and recursive solution

[@RC-qr8bn]

@@legatusmaximus6275 Thanks

[@alexkim8965]

Why is the last solution DFS Preorder? Shouldn't it be considered as Level Order (BFS)? It goes through nodes by each level (visit/process siblings first) before visiting its child. I understand people normally say Queue is BFS and Stack is DFS, but I don't understand this concept. They both look BFS to me whether they use queue or stack, because you visit the nodes from top to bottom, visit/process siblings first before visiting/processing its own child. It's a question I had for some time, hope someone can answer 😛

[@PrecisionWrittens]

That is only because the example tree doesn’t have much of a left side so the traversal gives the illusion of being BFS. However, say node 9 had children 4 and 8. Then we’d visit both 4 and 8 before 20 instead of going right from node 9 to 20. So it’s really just a crappy tree to use as an example bc it doesn’t differentiate BFS and DFS

[@abrarmahi]

Great video as always

[@nilshr2]

love you bro for great logical solutions

[@АнастасияМохор]

Thank you very much for your videos!

[@tanoybhowmick8715]

Thanks for the explanation.

[@Emorinken]

Thanks man, I appreciate

[@iancampbell8420]

3:40 “the max is clearly 2” idk man 1 seems pretty big

[@Ivan_lulz]

range(len(q)) bothered me a lot until I looked up that it was only evaluated at the start of the for loop.

[@khangton4382]

For this particular problem using DFS, why did we opt to use the max keyword? I don't understand the reasoning behind this.

[@sf-spark129]

It is always better to actually write down the recursive calls' results step by step. Then, you will see why you need max() in the return statement. It took me about 10 problems of Binary Tree until I see that naturally. To answer your question, DFS goes deeper and deeper(lower and lower) of the tree recursively until it reaches a leaf node(base case: root = None). From there, it starts building up like climbing up a tree. Let's say you have climbed a good amount on the left side of the tree and also a good amount on the right side. You really can't tell which side you climbed more. Then, max(left, right) will give you the higher side's height(depth) instantly. When you go one step higher, which (let's assume) is the root, then you will get the maximum height(depth) of the tree by 1 + max(left, right). Code I use to understand below: def maxDepth_DFS(self, root: Optional[TreeNode]) -> int: if not root: return 0 leftNode = self.maxDepth(root.left) rightNode = self.maxDepth(root.right) return max(leftNode, rightNode) + 1

[@sergii.golota]

I'm wondering how to transform list to a tree object? Is there a python code to do that?

[@YT.Nikolay]

check out this problem -> leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

[@josephavila3539]

Hello, thank you so much for your amazing content, I am devouring your insights and its helping me grow while gaining confidence. My question, for DFS and BFS, should it be ROOT in the answers opposed to NODE? Thank you.

[@QVL75]

Excellent explanation!

[@juanmacias5922]

I usually don't like recursion, but it was the simplest one. xD

[@sachitrao771]

good work sir

[@avtarchandra2407]

thankyou bro for adding the C++ codes on your website i do use fully your website .....and love you so much from India

[@NeetCode]

No problem, glad it's helpful!

[@amberchen5804]

Thank you for the awesome explanation. Where can I find the excel sheet at the beginning of your video? I liked the short solution hint

[@Sheik1388]

Can anyone please explain the syntax? I'm very new to OOP with Python, and I don't understand how we actually get the entire list of nodes (for instance "Input: root = [3,9,20,null,null,15,7]") through the treeNode class object which is not even a list...".

[@oliverheber599]

Its misleading, root is actually just 3 in that example, they shouldn't call the list root, the list is the entire tree, but only the root (3, with it's left and right (9,20) filled ) will be passed into the maxDepth function

[@sf-spark129]

For the BSF approach, you don't need base case if you code like this: Instead of using "if not root: return 0", q = deque([root]) if root else None will do just fine. This is more NeetCode-ish style of code I figured. Yes, you like to keep your code succinct although that can be sometimes difficult to follow. :) Code below: def maxDepth_BFS(self, root) -> int: q = deque([root]) if root else None level = 0 while q: for i in q: node = q.pop() if node.left: q.appendleft(node.left) if node.right: q.appendleft(node.right) level += 1 return level

[@samlinus836]

Simply awesome

[@anmolacharya309]

Can someone recommend me some visaulization platforms to see how the code and logic works together? For example, the recursive calls. I am not 100% with recursion so wanted to see it

[@manuchehrqoriev]

Thank you so much.

[@vatsalsharma5791]

Awesome explanation ❤️ Can you plz make a video on N Queens problem?

[@priceton_braswell]

hate to sound stupid but confused on this one. ive been understanding recursion pretty well but this problem says the input is a root node, but it looks like the input isn't just one node but multiple items in an array. so is the whole array being input as root or just the first one. if its the whole array. would if not root always be true and always return 0. please hellp

[@staceyonuora5329]

The input is the root node but the root node is an object of the class Tree node (the class is defined in comments in the video above the solution class ) which has 3 properties the value, the left node and the right node. You can access all the nodes of the tree just from the root node. I hope I was able to help

[@gottuparthiharichandana3381]

isn't the maximum depth same as the height of the tree?

[@Thejohnster1012]

final bit of code doesn't match up to drawing as it actually pops the right node first? correct me if wrong

[@dumbfailurekms]

you are correct. both work, but swap the order of how its pushed to stack to get pre order (NLR) This is technically an alternative pre order of NRL

[@dipakkumarrai1442]

Is there an equivalent Java version of implementing Max Depth of a tree using DFS/stack?

[@runeyman]

public int maxDepth(TreeNode root) { Stack stack = new Stack(); stack.add(new Pair(root, 1)); int depth = 0; while(!stack.isEmpty()){ Pair temp = stack.pop(); if(temp.treeNode != null){ depth = Math.max(temp.integer,depth); stack.add(new Pair(temp.treeNode.left, temp.integer + 1)); stack.add(new Pair(temp.treeNode.right, temp.integer + 1)); } } return depth; } public class Pair{ TreeNode treeNode; int integer; public Pair(TreeNode treeNode, int integer){ this.treeNode = treeNode; this.integer = integer; } }

[@aishwaryaranghar3385]

I loved this. Thanks sooo much.

[@fakeasfluff6842]

A stack in python can hold 2 elements?

[@milktea2755]

I believe the stack in Python is simply a list, and a list can hold individual elements, as well as tuples that hold two elements. This stack just holds a tuple of [node, depth] per node!

[@verayan2019]

could anyone explain why res = [0] instead of res = 0?

[@kedarnadh]

How stack bottom becomes stack top in 3rd approach. pls explain

[@ua9091]

Generally stack should start from bottom, but while explaining he started putting items at the top (like a table) which is actually the bottom of the stack.

[@thefuture5162]

0:36 😂 You are very funny brother

[@LongVu-sm8wm]

great, this is helpful.

[@indhumathi5846]

understood

[@ajayvishwanath1052]

Thanks!

[@NeetCode]

Thank you so much Ajay!!

[@choliu1918]

For some reason your BFS solition won’t pass this case on Leetcode today. [3,9,20,null,null,15,7]

[@MahdiHijazi]

The solution has a mistake, level should start from zero

[@hwang1607]

you are smart

[@rajivsarkar277]

Hi @NeetCode i am unable to grab the recursive and backtracking concept clearly.I have gone through all the videos but still unable to think about a solution using recusrsion and backtrack. will be of great help if u can guide me on the same

[@naveenprasanthsa3749]

He is not alive

[@nero9985]

@@naveenprasanthsa3749 Yes he is lol

[@director8656]

Do I even have to say anything, good video!

[@abhijitpai6085]

I lost it at 00:35

[@arnoldwolfstein]

in python we don't use camel case. it's snake case.

[@arnoldwolfstein]

for i range(len(q)). oh my

[@arnoldwolfstein]

buy thanks for the content

[@jonaskhanwald566]

lol. Breadth first search and depth first search are literally tongue twisters. Better say bfs and dfs.

[@day35ofdebuggingthesamelin56]

what do you mean? It's just depfarstsaerch and breithfasbtshsearsch.

[@sf-spark129]

don't forget 'f' in between like me...😂 imagine saying BS in the intervew

[@thelonerat9557]

5:07 I died

[@Dobby_zuul]

fyi, depth does NOT include the root (height of a tree does), the LeetCode description is wrong, root node is always at max depth 0.

[@amitjoshi7309]

I am not good with Recursion and tree thats why I cant even solve the simplest one liner solution...............

[@abh830]

create

[@dipanshusingh]

♥

[@jmbrjmbr2397]

I have a crush on you Neet..

[@vs3.14]

I did catch the node --> root. But ... here's what my aMaZiNg code resulted in - AttributeError: 'Solution' object has no attribute 'maxDeapth'. Did you mean: 'maxDepth'? **cries in the corner**

[@mjr6999]

Iterative Depfasajsdkdnf lol😂😂🙏🏻

[@bag_of_pixels]

bfs iterative solution is soo ugly, it's basically: while q: while q: curr = q.popleft()

[@1LineCode]

have a better explanation to leetcode-104 ((kzbin.info/www/bejne/o6OTg2xqbdqJeM0si=JuyxtZb0K1-j0UeG )), let me know if it helped

[@nginxgaming2778]

please speak slow you speak very fast I can't understand properly

[@szu-minyu3415]

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

[@mantrax314]

Thanks!