Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python
Video Overview & Insights
🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews
🚀 https://neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
🐦 Twitter: https://twitter.com/neetcode1
🥷 Discord: https://discord.gg/ddjKRXPqtk
Why insert null nodes in the stack in the iterative DFS solution? just check if node.left and node.right exist and add them if they do. Makes it simpler, cleaner and easier to reason about imo.
🐮 Support the channel: https://www.patreon.com/NEETcode
Twitter: https://twitter.com/neetcode1
thank you
Discord: https://discord.gg/ddjKRXPqtk
⭐ BLIND-75 SPREADSHEET: https://docs.google.com/spreadsheets/d/1A2PaQKcdwO_lwxz9bAnxXnIQayCouZP6d-ENrBz_NXc/edit#gid=0
Why use the deque for BFS but not iterative DFS? Isn't it more efficient than a list in both use cases -- as a queue and as a stack?
⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf
💡 CODING SOLUTIONS: https://www.youtube.com/playlist?list=PLot-Xpze53leF0FeHz2X0aG3zd0mr1AW_
I actually solved this problem on my own..
But I am here to listen and learn his explaining skill❤😊
💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1
🌲 TREE PLAYLIST: https://www.youtube.com/watch?v=OnSn2XEQ4MY&list=PLot-Xpze53ldg4pN6PfzoJY7KsKcxF1jg&index=2
one of the best creators for dsa with python i have seen so far
hope u wld reach 1mil soon
😇
💡 GRAPH PLAYLIST: https://www.youtube.com/watch?v=EgI5nU9etnU&list=PLot-Xpze53ldBT_7QA8NVot219jFNr_GI
💡 BACKTRACKING PLAYLIST: https://www.youtube.com/watch?v=pfiQ_PS1g8E&list=PLot-Xpze53lf5C3HSjCnyFghlW0G1HHXo
I just realized the last code does the right most bottom ones before the left ones, since it append/push L then R, son when pop will come out the R.
💡 LINKED LIST PLAYLIST: https://www.youtube.com/watch?v=G0_I-ZF0S38&list=PLot-Xpze53leU0Ec0VkBhnf4npMRFiNcB&index=2
Problem Link: https://neetcode.io/problems/depth-of-binary-tree
Commenting for the algo. Thank you for the video.
0:00 - Read the problem
1:28 - Recursive DFS
I'm getting this for the BFS solution
Traceback (most recent call last):
File "/box/script.py", line 95, in <module>
output = solution.maxDepth(root)
^^^^^^^^^^^^^^^^^^^^^^^
File "/box/script.py", line 35, in maxDepth
if node.left:
^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'left'
5:30 - BFS Solution
10:43 - Iterative DFS
thanks :)
leetcode 104
This question was identified as an interview question from here: https://github.com/xizhengszhang/Leetcode_company_frequency
Navdeep, you are the GOAT 😭🙏🙏🙏
#binary #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.
BFS memory complexity is les than dfs : in bfs the max number of nodes in memory is equal to the level which has the max of nodes (but unable to compute it )
More User Perspectives
the benefit of no using recursion bc in big trees you can run out of stack space and get a stack overflow
@idriskas5:08 LMAOOOOOOOO
@SURYAPAVANDEVARAPALLIBRO CANT EVEN SOLVE EASY PROBLEMS
DELETE IDE BRO
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 ?
@divyashukla4321please speak slow you speak very fast I can't understand properly
@nginxgaming2778have a better explanation to leetcode-104 ((https://youtu.be/mr0R948uVBk?si=JuyxtZb0K1-j0UeG )), let me know if it helped
@1LineCodeNeetcode simplifying leetcode, cheers man!
@giancarlokuosmanen9723How is the first soluton's memory complexity same as the other two's when we don't use additional data structure (deque or stack)?
@draugno7What's the diffference between bfs and iterative dfs?
@haha-hs7yfThanks man, I appreciate
@Emorinken3:40 “the max is clearly 2” idk man 1 seems pretty big
@iancampbell8420Can 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
@anmolacharya309Thanks!
@mantrax31410: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
@suri4Musiqfyi, depth does NOT include the root (height of a tree does), the LeetCode description is wrong, root node is always at max depth 0.
@Dobby_zuulIn 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?
@EdenObengNanaKyeiDo we really need the for loop inside the iterative bfs algorithm? Esp when this is a binary tree?
@suri4MusiqThank 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..
@grigorypiskunov418range(len(q)) bothered me a lot until I looked up that it was only evaluated at the start of the for loop.
@Ivan_lulz0:36 😂 You are very funny brother
@thefuture5162Another 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())
I am not good with Recursion and tree thats why I cant even solve the simplest one liner solution...............
@amitjoshi7309BFS 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
@theFifthMountain123I have a crush on you Neet..
@jmbrjmbr000Thank you for the clear explanation! You are wonderful :)
@szu-minyu3415in python we don't use camel case. it's snake case.
@arnoldwolfsteinHow do you create these videos like on iPad or on the computer as its difficult to drawing otherwise ?
@abh830create
@abh830Great video as always
@abrarmahiI had only coded up the recursive way, but good to know about the other 2 ways you described in this video
@syafzal273Thank you very much for your videos!
@АнастасияМохорThank you so much.
@manuchehrqorievThe explanation is very good. Please let me know where I can get this code. Please share the link
@srisai-j4kHey 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
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*
Wooow... almost one line solution ))) You are amazing!!!
@kirillzlobin7135I usually don't like recursion, but it was the simplest one. xD
@juanmacias5922you are smart
@hwang1607