Test If A Binary Tree Is Height Balanced ("Balanced Binary Tree" on LeetCode)
ฝัง
- เผยแพร่เมื่อ 23 ส.ค. 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 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.
![เบิ้ล ปทุมราช - สาวสอง ( มีมี่ของอ้าย ) ft. ตาต้า,ต้องเต [OFFICIAL MV]](http://i.ytimg.com/vi/mqlMjnP08XI/mqdefault.jpg)
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 th-cam.com/video/lbnoG2dsUk0/w-d-xo.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
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!
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
OMG the way you explain the idea behind why the algorithm works, it just blew me away. Thanks a lot mate!
wassup
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
Loved that idea of "asking a question".Thanks man!!
ye
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.
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
great way of explaining stuff...Keep up the good work...you folks are as valuable as nation's best teachers.
you get so into explaining this, gotta love the head scratch lmao
thanks for an awesome explanation :D
lol wut
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
Man, you should train CS professors at universities on how to teach algorithms
nah
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!
What you are doing is nothing short of humanitarian work my friend!
ye
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
undoubtedly, the best explanation of how recursion works in trees
What a smart and attractive illustration, well-done man!
thanks
That's gangsta as fuck we need more of this
haha
you are so gifted at teaching, never stop!
I am so glad that I found your channel on TH-cam...! Thank You very Much Sir!
welcome
Awesome explanation! Trees are speaking for themselves :D
ye
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 😀
Finally a clear cut video good job!
thanks
Thank you man! This video really helps me to understand the process of solving the problem.
sure
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.
Really detailed and clear explanation! Thank you!!!
sure
You said the code was below, but I cannot find it.
awesome work bro!! helped a lot in visualization of recursion calls
EXCELLENT explanation. extremely clear
thanks, I like you
Thank you very much sir, your channel will soon be on the top.
thanks
Great video, thanks. Appreciate the table of contents.
May you flourish
Great job! You explained this well
Very cool approach with the nodes which are "bellow sea level". 😊
hahaha
at 6:00 I was like, say no more => Subscribed.
fkn love the way explain stuff man
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.
WHAT! Did you just teach me recursion? I thought it was impossible!
Best interview prep ever :)
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/
Made your 2K to 2.1K...
Thanks for the brief explanation!
awesome explination , i love the way you explain things.
thx
Amazing explanation, thank you! :)
Thank you so much for this beautiful explanation 🙏
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.
I love u your videos so much! Thank you so much for your time and work!
The node which is marked red cross will not return 2. It breaks the call there only.
ok
you explained this so well. wow.
*subscribed :)
thanks!
Hey, really a great explanation man! It'd be awesome if you could whiteboard the pseudocode too after the explanation.
yeah good idea
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
really nice job on explaining Balanced Binary Tree!
thanks
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
This video was fireeee I hate recursion but this visualization and explanation really helped
This explanation is so clear so good!
glad it helped
Nice explanation! Thank you!
wow, your teaching is amazing! thanks again!
very detailed explaination brada love u
sure homie
Great explanation! Do you have a link to the code for this problem that I can refer to?
excellent explanation!! thank you!
Amazing teaching!
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
thanks lad, much appreciated!
May I ask what the complexity of the non-efficient way you mentioned in the beginning of the video is?
Quadratic O(n^2)
we can simply check whether each node has left and right node?
can you explain about that
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 from France !
sure! 🇫🇷
Your explanation is somehow kinda funny (in a good way)!
yeah I was weird when the channel started. no one was watching
Great explanation, thanks a lot :)
Finally got an awesome explanation 🏆
where is the code ?
thank you much ,I totally uderstand how recursion work
nice
very helpful. thank you!
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=AllNaturale11 🎉
nice video!!! thanks!!
sure
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
have you done the code for this anywhere?! loved the video
I think so here: github.com/bephrem1/backtobackswe
love this! thank you
I'm having trouble finding the code in the description! :(
The repository is deprecated - we only maintain backtobackswe.com now.
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.
this dude kills it
the time complexity is wrong, it should be O(n*log n), n is for getting height for each node and you need to check every node for balanced is log n.
The worst case could be O(n^2) in this top-down solution, actually.
If the tree is skewed height checking is O(n)
@@BackToBackSWE Yes, and you not only check the height, but also check the balanced, which will cost O(log n). The total time complexity should be O(n log n) leetcode.com/problems/balanced-binary-tree/solution/
That 8:40 zoom is gold hahahaha
what did I do
A big thank you for this content
thanks for being here
Best explanation!
How can someone explain this clearly wow you really helped me..
thanks
nice
people like u save students like us😃
May I ask where is the code? you mentioned it is in description but it is not...
Do check out backtobackswe.com/platform/content
That helped, thanks.
sure
Lifesaver : ) Thank you so much!! Best explanation ever!!
sure
What's the difference between this and an AVL tree?
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
Bro you are awesome , love from India
much love
Thanks 🙏
sure
Thanks
where can i find the code in the website??plz tell me
The repository is deprecated - we only maintain backtobackswe.com now.
Bro, Can you tell me where the code is?
We only maintain solutions on backtobackswe.com (paywall)
This guy is awesome 👏
I'm ok.
great work brother
Ok, I accept that I agreed to max(0,0) = 1. @ 8:40
ok
Would a tree be considered balanced tree if the root have only one node at one side ?