Test If A Binary Tree Is Height Balanced ("Balanced Binary Tree" on LeetCode)
HTML-код
- Опубликовано: 20 янв 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program that takes the root of a binary tree as input and checks whether the tree is height-balanced.
A tree is height balanced if for each node in the tree, the difference in the height of its left and right subtrees is at most one.
Approach 1 (Get Height Of Tree Rooted At Each Node)
We can perform a traversal of the tree and at each node get the height of its left and right subtrees.
This wastes time as we will be repeating work and the traversal of nodes.
Approach 2 (Drill Down With Recursion And Respond Back Up)
We can notice that we don't need to know the heights of all of the subtrees all at once.
All we need to know is whether a subtree is height balanced or not and the height of the tree rooted at that node, not information about any of its descendants.
Our base case is that a null node (we went past the leaves in our recursion) is height balanced and has a height of -1 since it is an empty tree.
So the key is that we will drive towards our base case of the null leaf descendant and deduce and check heights on the way upwards.
Key points of interest:
1.) Is the subtree height balanced?
2.) What is the height of the tree rooted at that node?
Complexities
Time: O( n )
This is a postorder traversal (left right node) with possible early termination if any left subtree turns out unbalanced and an early result bubbles back up.
At worst we will still touch all n nodes if we have no early termination.
Space: O( h )
Our call stack (from recursion) will only go as far deep as the height of the tree, so h (the height of the tree) is our space bound for the amount of call stack frames that we will create
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 10.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. 
Наука
Table of Contents:
The Problem Introduction 0:00 - 0:33
Cases That Are Height Balanced 0:33 - 1:56
Cases That Are NOT Height Balanced 1:56 - 2:58
Approach #1: Get Heights of Subtrees At Each Node 2:58 - 3:46
Approach #2: Recurse To Base Cases 3:46 - 4:23
Walkthrough of The Recursion 4:23 - 12:39
Time Complexity 12:39 - 13:25
Space Complexity 13:25 - 13:39
Wrap Up 13:39 - 13:57
The teacher's notes contain a link to the code for the problem discussed in the video. It is fully commented for teaching purposes strictly.
You're really amazing, I was enjoying your teaching. Thanks a lot for this high-quality teaching for free.
great to hear!!!
Where is the code?
Where is code
Could not find the link to the code :(
Me on Tinder: Hey, what is your height? And are you balanced?
ye
@@BackToBackSWE i am average height
Balanced here might mean whether your tootsiroll matches your height
@@johnpaul4301 ruclips.net/video/lbnoG2dsUk0/видео.html
Sharing this channel to all my friends who are interested to learn data structure algorithm .. Please make more videos on Data Structure and algorithms .. Believe me nobody tech like you. This channel has potential to become one of the best. The difference between you and others, is that most people just jumps directly into the solution but you tell us 'the thought process', 'how to interpret the problem' which are most important. Your think loud approach is best part. Please don't stop making such video. People like me are always with you.
Haha thanks
yes!!
Better than my data structures professor, thank you
thx
OMG the way you explain the idea behind why the algorithm works, it just blew me away. Thanks a lot mate!
wassup
Thanks for the videos! They're very well done compared to most of the others where people either start writing code immediately or jump straight to the solution without explaining how they got there.
Sure, this channel still has a long way to go
You deserve way way more recognition and credit for the work you have done sir!
better than any college professor I have had.
thanks and thx
you get so into explaining this, gotta love the head scratch lmao
thanks for an awesome explanation :D
lol wut
Loved that idea of "asking a question".Thanks man!!
ye
asking the "critical question" and then returning the answer to that question to my parent is a great way to reason about recursion in general
your teaching style sir is on another level!!!
thanks!
great way of explaining stuff...Keep up the good work...you folks are as valuable as nation's best teachers.
you are so gifted at teaching, never stop!
awesome work bro!! helped a lot in visualization of recursion calls
you're a remarkable teacher. blew my PhD data structures professor out of the water, honestly. thank you for making these videos. I'm surviving interview season bc of this.
lol nice, sure sure, they are a relic of the past self. I don't even remember recording some of these. Nice nice, you'll make it yo
undoubtedly, the best explanation of how recursion works in trees
Your explanation is the best i have ever seen and really helps to understand these difficult problems. I appreciate your selfless work and the dedication with which you teach us these topics..Got to learn a lo from you,keep uploading more videos and soon this channel would turn out to be the best resource for interview preparation.
thx
Thank you man! This video really helps me to understand the process of solving the problem.
sure
Thank you very much. I myself teach myself to code, I'm also a teacher in kindergarten. I recognize a lot of myself in you. Keep up the good work!
Nice! thanks!
I am so glad that I found your channel on RUclips...! Thank You very Much Sir!
welcome
Great job! You explained this well
What a smart and attractive illustration, well-done man!
thanks
What you are doing is nothing short of humanitarian work my friend!
ye
Really detailed and clear explanation! Thank you!!!
sure
Finally a clear cut video good job!
thanks
Made your 2K to 2.1K...
Thanks for the brief explanation!
Great video, thanks. Appreciate the table of contents.
May you flourish
Thank you very much sir, your channel will soon be on the top.
thanks
Awesome walkthrough! Gave me a nice intuition on how I would write the code. Do you think you could make a video on how to insert a node into a BBST?
Nice. and maybe.
That's gangsta as fuck we need more of this
haha
I love u your videos so much! Thank you so much for your time and work!
Great explanation! Do you have a link to the code for this problem that I can refer to?
You said the code was below, but I cannot find it.
The way you explain everything man…the number of times you revisit some moments is perfect, the speed with which you explain the material is perfect. Keep up the good work and thank you for teaching us such important topics in such a great way.
excellent explanation!! thank you!
Nice explanation! Thank you!
EXCELLENT explanation. extremely clear
thanks, I like you
wow, your teaching is amazing! thanks again!
Man, you should train CS professors at universities on how to teach algorithms
nah
thanks lad, much appreciated!
awesome explination , i love the way you explain things.
thx
really nice job on explaining Balanced Binary Tree!
thanks
Such a good explanation, you’re the best!
Happy Holidays! Really glad to help 🎉 Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/
Very cool approach with the nodes which are "bellow sea level". 😊
hahaha
Awesome explanation! Trees are speaking for themselves :D
ye
Great explanation, thanks a lot :)
This video was fireeee I hate recursion but this visualization and explanation really helped
Hey, really a great explanation man! It'd be awesome if you could whiteboard the pseudocode too after the explanation.
yeah good idea
Best interview prep ever :)
thanks
Dude! I am not seeing the code in the down :(
could you please update the Link
The repository is deprecated - we only maintain backtobackswe.com now.
we can simply check whether each node has left and right node?
can you explain about that
why this has so less views??! No one these days teaches like this guy...not even my professor does....this video helped me creating a foundation for my data structure course
ye
This explanation is so clear so good!
glad it helped
Amazing explanation, thank you! :)
you explained this so well. wow.
*subscribed :)
thanks!
WHAT! Did you just teach me recursion? I thought it was impossible!
May I ask what the complexity of the non-efficient way you mentioned in the beginning of the video is?
Quadratic O(n^2)
love this! thank you
very detailed explaination brada love u
sure homie
at 6:00 I was like, say no more => Subscribed.
fkn love the way explain stuff man
Thank you so much for this beautiful explanation 🙏
Finally got an awesome explanation 🏆
What's the difference between this and an AVL tree?
ur explanation is so concise that my golden retriever can now display his treats in tree structure
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Hey
Could you please help me to figure out the complexity of my solution of this problem? It shows +- the same performance as your's on the Leetcode, but I'm not sure neither about space nor about time complexity
```
public class Solution110 {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) - height(root.right))
This does what I described at 2:58. You can give it a upper bound of O(n^2). Here is my logic:
My Logic:
#1 The tree has n nodes
#2 The isBalanced() function will be called on all n nodes worst case if the tree IS balanced
#3 The height() function runs in Linear time with respect the amount of nodes in the subtree of the node passed to it
#4 When height() is called, every node in root's subtree will get height() called on it further justifying #3
#5 So based on #1, we will be doing O( n * whatever work we do at each node )
#6 In #3 we established height() runs in linear time with respect to the amount of nodes below and including root. So each call of height() from isBalanced() will do a fractional amount of work of n. O( fraction of n * n ) = O(n). Still linear even if we basically cut the amount of nodes in half by going to the left and right subtrees.
#7 Because of #1, #5, and #6, we can provide an upper bound of Linear work for an amount of n nodes. O( n * n ) = O(n^2)
This is my logic as it stands now. I can be incorrect because of the faulty nature of any of the above understandings. Please try to prove me wrong, because I am not always right. Challenge my understand as well as yours.
Also to address "It shows +- the same performance as your's on the Leetcode, but I'm not sure neither about space nor about time complexity"...do not look at Elapsed Real Time to assess time complexity. Especially for Leetcode solutions. You HAVE to use LARGE n values. This is why it is called "asymptotic analysis".
See this: ruclips.net/video/myZKhztFhzE/видео.html
I just don't get why its max(-1,-1)+1, is that supposed to be equivalent to taking absolute value? if so can you explain please
I am just simulating the code as it would execute the base case.
Hey bro, I want you to explain "Median in a stream of integers (running integers)" this problem. I am unable to understand why we need to use self balanced binary tree to solve this problem. Thanks. I will be helpful.. You explain better than any other.
I'll be covering that in my class but not on the channel, most of my technical videos will go there now. I'm going to convert the channel into a more "I'm building things" type thing soon
hey! love your videos! one question, can't i just check the absolute height difference from each node? without asking are you balanced to each node?
Yes but that will duplicate subtree measurements
if it has to fail, it will always fail at the root node right? can you provide with a counterexample to what I said?
Exactly, it doesnt wkrk
thank you much ,I totally uderstand how recursion work
nice
where is the code ?
Your explanation is somehow kinda funny (in a good way)!
yeah I was weird when the channel started. no one was watching
nice video!!! thanks!!
sure
A big thank you for this content
thanks for being here
very helpful. thank you!
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=AllNaturale11 🎉
this dude kills it
I'm having trouble finding the code in the description! :(
The repository is deprecated - we only maintain backtobackswe.com now.
I'm kinda late idk if you'll respond to this comment
first of all thanks for your efforts.
second thing ... as far as I know ( and i almost know nothing yet, I'm just a beginner), something doesn't add up in the last example
Dont we consider a tree a Balanced tree if the absolute difference of the heights of each side is
Best explanation!
The node which is marked red cross will not return 2. It breaks the call there only.
ok
Thank you from France !
sure! 🇫🇷
have you done the code for this anywhere?! loved the video
I think so here: github.com/bephrem1/backtobackswe
That helped, thanks.
sure
A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by no more than 1.
Would a tree be considered balanced tree if the root have only one node at one side ?
Thanks
great work brother
How can someone explain this clearly wow you really helped me..
thanks
nice
wow you are super good!
where can i find the code in the website??plz tell me
The repository is deprecated - we only maintain backtobackswe.com now.
Could you just do a breadth search and if the count of children at a level count is odd, it is not balanced?
How would this work exactly?
@@BackToBackSWE well it seemed like possibly a feature of an unbalanced binary tree is it would have a level with non-even count of nodes. Unless i am misunderstanding what a balanced tree should look like (which is possible). So you just make a queue and walk down the nodes, pushing children at each. If your total count of children in the queue is ever odd at each step then you know the tree is unbalanced. Not sure if that would work or not though, just pondering
thanku so so much man....
Lifesaver : ) Thank you so much!! Best explanation ever!!
sure
Why add 1 to max(heightOfRightNode, heightOfLeftNode) ?, Wha's the logic here??
Including the node that the call is working on in the height as the calls go up
May I ask where is the code? you mentioned it is in description but it is not...
Do check out backtobackswe.com/platform/content
This guy is awesome 👏
I'm ok.
Thanks 🙏
sure
Bro you are awesome , love from India
much love
people like u save students like us😃
where is the code
Cant understand why are we adding 1.