Balanced Binary Tree | LeetCode 110 | Coding Interview Tutorial
Vložit
- čas přidán 26. 07. 2024
- Balanced Binary Tree solution: LeetCode 110
Code and written explanation: terriblewhiteboard.com/balanc...
Link to problem on LeetCode: leetcode.com/problems/balance...
Buy Me a Coffee: www.buymeacoffee.com/terrible...
AFFILIATE LINKS
If you're interested in learning algorithms, these are great resources.
💻 40% off Tech Interview Pro: techinterviewpro.com/terriblew...
⌨️ 20% off CoderPro: coderpro.com/terriblewhiteboard
💲 All coupons and discounts 💲
terriblewhiteboard.com/coupon...
Balanced Binary Tree | LeetCode 110 | Coding Interview
#balancedbinarytree #leetcode #algorithms #terriblewhiteboard #codinginterview
Click the time stamp to jump to different parts of the video.
00:00 Title
00:06 Problem readout
00:51 Whiteboard solution
11:16 Coding solution
19:43 Result and outro
If there are any videos you'd like me to make or if you have any ideas on how to optimize this solution, let me know!
You should continue making such videos. The explaination was spot on. Really helpful. Your channel will soon become one of the top interview prep channels. Good Luck and thanks.
Thanks!
This was one of the best LeetCode explanations I have ever watched!
Thank you for this video. The explanation was really helpful.What would be time and space complexity of this problem?
Every node is visited once, so time complexity should be O(n). The return statements should be called once per node, so the space complexity should be O(n) as well. Let me know if you see it differently!
Your videos are incredibly comprehensive and helpful! When I land a job as a dev I will be able to contribute to your Patreon. I am going to share your blog with other aspiring devs.
Thanks and good luck in your dev journey!
I seriously love your videos! Please keep making them :D
Vid request: Could you please make 108 in javasript as well?
@terrible whiteboard make videos on hashmap(pls...pls...pls..)
I'll add it to the list!
shouldn't it stop once it returns negative 1 @18.16
nice explanation at the end
Nice. Just to point out one issue, when you are walking through the code, we don't always start from Line 21- because the stack will ideally unwind and return control to the previous stackframe on Line 25. So on and so forth.
Thanks Whiteboard... your not that terrible dude hahaha
Thanks!
Why does recursion check from bottom to top (4, 3, 2, 1) instead of top to bottom (1, 2, 3, 4) ? Shouldn't it start from top to bottom if root = 1?
Also, how would you console log a binary tree to check each height?
That's is exactly my question too.
took me forever to get this
Absolutely amazing approach. Thanks for the video. When I read the challenge description I don't even know where to start from. Yet you draw a picture first to figure what you are going to do and then you turn it into code. How do you do that man? Did you just use LeetCode to practice tons of algorithms? When I open some challenge and read the prompt nothing clicks in my head.
Hello! These videos aren't me figuring out the solutions live. Think of them more as tutorials than live coding. If you look at the clock in the iPad, you can see they take hours to film.
You're welcome, though!
how does the tree have a right side of one if they all none on the right side??
Wouldn't this break if you have mirrored imbalance? Ex: here, it goes 1, 2, 3, 4 all the way down the left. What if you also had 1, 5, 6, 7 down the right (i.e. a line the exact same height down the opposite side)? It should return balanced, right? But wouldn't that fail?
Both sides would return -1 up to the level below the root (where the 2 currently is, and the 5 could be). The || check would find one -1, so it would say that the tree is unbalanced. But it's not. Both sides are the exact same height of 4, the left being (1, 2, 3, 4) and the right being (1, 5, 6, 7).
You'd need an && (and) check to see if both left and right are -1. Only, wouldn't that also fail? At the (2, 5) level, we don't know what the actual height below it is, only that it's imbalanced. So, if we extend the right side by several nodes to (1, 5, 6, 7, 8, 9, 10), it would still only return -1. The function would treat both sides as equally unbalanced, even though they're not the same height.
Instead, wouldn't it be more thorough to return the actual height? The recursive structure remains the same, but instead of a -1, we just return the max of the actual heights so at the end, we know the longest chain on both left and right sides. With those, we can compare directly, and no edge cases like this escape.
Now, it's highly possible I missed something, but I wanted to share this and see what others thought.
In this case the tree would be visually symmetrical, yes, but even if we look at either left child or right child we would see that the height difference between their subtrees is more than 1 and the whole tree is considered unbalanced if at least one of its subtrees is unbalanced. So in this case both of its children are unbalanced. And honestly I would go with a boolean false instead of -1 because it's very confusing since we are also calculating the height by adding 1 for a node (1 node is considered to be the height of 1) and it's confusing because -1 is used as a boolean here and doesn't play a role in calculating the height.