Test If A Binary Tree Is Height Balanced ("Balanced Binary Tree" on LeetCode)
Вставка
- Опубліковано 19 вер 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.
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 ua-cam.com/video/lbnoG2dsUk0/v-deo.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!
OMG the way you explain the idea behind why the algorithm works, it just blew me away. Thanks a lot mate!
wassup
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
Loved that idea of "asking a question".Thanks man!!
ye
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'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
you get so into explaining this, gotta love the head scratch lmao
thanks for an awesome explanation :D
lol wut
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.
Man, you should train CS professors at universities on how to teach algorithms
nah
That's gangsta as fuck we need more of this
haha
great way of explaining stuff...Keep up the good work...you folks are as valuable as nation's best teachers.
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
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
What a smart and attractive illustration, well-done man!
thanks
What you are doing is nothing short of humanitarian work my friend!
ye
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!
Really detailed and clear explanation! Thank you!!!
sure
you are so gifted at teaching, never stop!
Finally a clear cut video good job!
thanks
Awesome explanation! Trees are speaking for themselves :D
ye
I am so glad that I found your channel on UA-cam...! Thank You very Much Sir!
welcome
EXCELLENT explanation. extremely clear
thanks, I like you
Very cool approach with the nodes which are "bellow sea level". 😊
hahaha
undoubtedly, the best explanation of how recursion works in trees
The node which is marked red cross will not return 2. It breaks the call there only.
ok
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.
Thank you man! This video really helps me to understand the process of solving the problem.
sure
You said the code was below, but I cannot find it.
Great video, thanks. Appreciate the table of contents.
May you flourish
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.
Best interview prep ever :)
thanks
awesome work bro!! helped a lot in visualization of recursion calls
Great job! You explained this well
Made your 2K to 2.1K...
Thanks for the brief explanation!
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
Thank you very much sir, your channel will soon be on the top.
thanks
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, really a great explanation man! It'd be awesome if you could whiteboard the pseudocode too after the explanation.
yeah good idea
awesome explination , i love the way you explain things.
thx
at 6:00 I was like, say no more => Subscribed.
fkn love the way explain stuff man
really nice job on explaining Balanced Binary Tree!
thanks
you explained this so well. wow.
*subscribed :)
thanks!
wow, your teaching is amazing! thanks again!
WHAT! Did you just teach me recursion? I thought it was impossible!
Here is the code
github.com/bephrem1/backtobackswe/blob/master/Trees%2C%20Binary%20Trees%2C%20%26%20Binary%20Search%20Trees/HeightBalancedBinaryTree/HeightBalancedBinaryTree.java
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/
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.
thank you much ,I totally uderstand how recursion work
nice
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
Amazing explanation, thank you! :)
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
That 8:40 zoom is gold hahahaha
what did I do
very detailed explaination brada love u
sure homie
How can someone explain this clearly wow you really helped me..
thanks
nice
Your explanation is somehow kinda funny (in a good way)!
yeah I was weird when the channel started. no one was watching
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/
Nice explanation! Thank you!
This explanation is so clear so good!
glad it helped
nice video!!! thanks!!
sure
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
Thank you from France !
sure! 🇫🇷
Amazing teaching!
This video was fireeee I hate recursion but this visualization and explanation really helped
May I ask what the complexity of the non-efficient way you mentioned in the beginning of the video is?
Quadratic O(n^2)
i hav to pause the video and say GOD to you.... You are GOD!!!!! 😇😇
i try, i try
I love u your videos so much! Thank you so much for your time and work!
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
Ok, I accept that I agreed to max(0,0) = 1. @ 8:40
ok
have you done the code for this anywhere?! loved the video
I think so here: github.com/bephrem1/backtobackswe
this dude kills it
people like u save students like us😃
Great explanation! Do you have a link to the code for this problem that I can refer to?
Thanks
thanks lad, much appreciated!
where is the code ?
very helpful. thank you!
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=AllNaturale11 🎉
Finally got an awesome explanation 🏆
Thanks 🙏
sure
That helped, thanks.
sure
Best explanation!
love this! thank you
great work brother
A big thank you for this content
thanks for being here
Dude please include in your videos bro that would be of great help!
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
we can simply check whether each node has left and right node?
can you explain about that
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.
Nice explanation. The video editing is distracting though.. Has a frenetic feel, which isn't conducive to learning something for the first time.
noted
What's the difference between this and an AVL tree?
My goto channel for any problem
hey
I'm having trouble finding the code in the description! :(
The repository is deprecated - we only maintain backtobackswe.com now.
iterative approach is trickier. one fucker asked me in an interview.
Bro you are awesome , love from India
much love
where can i find the code in the website??plz tell me
The repository is deprecated - we only maintain backtobackswe.com now.
wow you are super good!