Test If A Binary Tree Is Height Balanced ("Balanced Binary Tree" on LeetCode)

Поділитися
Вставка
  • Опубліковано 21 гру 2024

КОМЕНТАРІ •

  • @BackToBackSWE
    @BackToBackSWE  6 років тому +30

    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.

  • @BismaSuleman
    @BismaSuleman 4 роки тому +80

    Me on Tinder: Hey, what is your height? And are you balanced?

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому +5

      ye

    • @ExplorerSpace
      @ExplorerSpace 3 роки тому

      @@BackToBackSWE i am average height

    • @johnpaul4301
      @johnpaul4301 3 роки тому

      Balanced here might mean whether your tootsiroll matches your height

    • @WyMustIGo
      @WyMustIGo 3 роки тому

      @@johnpaul4301 ua-cam.com/video/lbnoG2dsUk0/v-deo.html

  • @rban123
    @rban123 5 років тому +74

    Better than my data structures professor, thank you

  • @stephyjacob1256
    @stephyjacob1256 5 років тому +70

    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.

  • @josephwong2832
    @josephwong2832 4 роки тому +5

    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!!!

  • @turnuptheMIKEG
    @turnuptheMIKEG 4 роки тому +2

    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.

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому +1

      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

  • @adityajain-fn6ne
    @adityajain-fn6ne 4 роки тому +12

    You deserve way way more recognition and credit for the work you have done sir!
    better than any college professor I have had.

  • @nikhilkumarmishra1225
    @nikhilkumarmishra1225 5 років тому +7

    OMG the way you explain the idea behind why the algorithm works, it just blew me away. Thanks a lot mate!

  • @ahiduzzamanahir1338
    @ahiduzzamanahir1338 3 роки тому +1

    WHAT! Did you just teach me recursion? I thought it was impossible!

  • @rakhman8621
    @rakhman8621 Рік тому +2

    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.

  • @psthakur1199
    @psthakur1199 4 роки тому +5

    Loved that idea of "asking a question".Thanks man!!

  • @rahoolification
    @rahoolification 4 роки тому +1

    What you are doing is nothing short of humanitarian work my friend!

  • @realmarciomarinho
    @realmarciomarinho 3 роки тому +2

    You said the code was below, but I cannot find it.

  • @priyogopalsingha3487
    @priyogopalsingha3487 2 роки тому

    undoubtedly, the best explanation of how recursion works in trees

  • @adenosinetp10
    @adenosinetp10 4 роки тому +1

    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

  • @PherricOxide
    @PherricOxide 5 років тому +4

    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.

    • @BackToBackSWE
      @BackToBackSWE  5 років тому

      Sure, this channel still has a long way to go

  • @hugenerretho9151
    @hugenerretho9151 2 роки тому

    ur explanation is so concise that my golden retriever can now display his treats in tree structure

    • @BackToBackSWE
      @BackToBackSWE  2 роки тому

      Thank you, glad you liked it 😀
      Do check out backtobackswe.com/platform/content
      and please recommend us to your family and friends 😀

  • @ggzz8845
    @ggzz8845 3 роки тому +3

    where is the code ?

  • @johnmcway6120
    @johnmcway6120 4 роки тому +3

    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!

  • @MuhammadIrshadAli
    @MuhammadIrshadAli 4 роки тому +6

    Man, you should train CS professors at universities on how to teach algorithms

  • @kunpeng8646
    @kunpeng8646 4 роки тому +2

    What a smart and attractive illustration, well-done man!

  • @afsinyilmaz8665
    @afsinyilmaz8665 3 роки тому +2

    great way of explaining stuff...Keep up the good work...you folks are as valuable as nation's best teachers.

  • @ruthylevi9804
    @ruthylevi9804 3 роки тому +1

    you are so gifted at teaching, never stop!

  • @missrockinout
    @missrockinout 5 років тому +10

    you get so into explaining this, gotta love the head scratch lmao
    thanks for an awesome explanation :D

  • @deepamkumar5211
    @deepamkumar5211 4 роки тому +3

    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.

  • @randalllionelkharkrang4047
    @randalllionelkharkrang4047 3 роки тому +1

    if it has to fail, it will always fail at the root node right? can you provide with a counterexample to what I said?

  • @wowzande
    @wowzande 5 років тому +2

    That's gangsta as fuck we need more of this

  • @HemanthaKumarYadav
    @HemanthaKumarYadav 4 роки тому +1

    I am so glad that I found your channel on UA-cam...! Thank You very Much Sir!

  • @Don_ron666
    @Don_ron666 5 років тому +2

    Finally a clear cut video good job!

  • @amitmishra2736
    @amitmishra2736 4 роки тому +7

    Dude! I am not seeing the code in the down :(
    could you please update the Link

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      The repository is deprecated - we only maintain backtobackswe.com now.

  • @aatifnazar1766
    @aatifnazar1766 5 років тому +2

    The node which is marked red cross will not return 2. It breaks the call there only.

  • @リンゴ酢-b8g
    @リンゴ酢-b8g 2 роки тому

    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.

  • @SOURAVKUMAR-tw3ds
    @SOURAVKUMAR-tw3ds 3 роки тому

    awesome work bro!! helped a lot in visualization of recursion calls

  • @nandanimadhukar
    @nandanimadhukar 4 роки тому +4

    Awesome explanation! Trees are speaking for themselves :D

  • @doruwyl
    @doruwyl 5 років тому +1

    Very cool approach with the nodes which are "bellow sea level". 😊

  • @TacklessNebula3
    @TacklessNebula3 3 роки тому

    Made your 2K to 2.1K...
    Thanks for the brief explanation!

  • @quirkyquester
    @quirkyquester 4 роки тому +1

    Thank you man! This video really helps me to understand the process of solving the problem.

  • @ramizrizwan3057
    @ramizrizwan3057 2 роки тому

    Such a good explanation, you’re the best!

    • @BackToBackSWE
      @BackToBackSWE  2 роки тому

      Happy Holidays! Really glad to help 🎉 Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/

  • @sankethb.k642
    @sankethb.k642 5 років тому +1

    Thank you very much sir, your channel will soon be on the top.

  • @wellingtonzane4288
    @wellingtonzane4288 5 років тому +3

    Really detailed and clear explanation! Thank you!!!

  • @syedmdharris8814
    @syedmdharris8814 4 роки тому

    we can simply check whether each node has left and right node?
    can you explain about that

  • @kevinandres3306
    @kevinandres3306 5 років тому +2

    EXCELLENT explanation. extremely clear

  • @baraaabuasal5626
    @baraaabuasal5626 6 місяців тому

    at 6:00 I was like, say no more => Subscribed.
    fkn love the way explain stuff man

  • @stargazer8718
    @stargazer8718 2 роки тому

    What's the difference between this and an AVL tree?

  • @nishanth998
    @nishanth998 4 роки тому +1

    where can i find the code in the website??plz tell me

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      The repository is deprecated - we only maintain backtobackswe.com now.

  • @maripaz5650
    @maripaz5650 4 роки тому +2

    Best interview prep ever :)

  • @max500k
    @max500k 3 роки тому +1

    Great job! You explained this well

  • @abhishekk.3977
    @abhishekk.3977 4 роки тому +2

    Ok, I accept that I agreed to max(0,0) = 1. @ 8:40

  • @researchandbuild1751
    @researchandbuild1751 4 роки тому +1

    Could you just do a breadth search and if the count of children at a level count is odd, it is not balanced?

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      How would this work exactly?

    • @researchandbuild1751
      @researchandbuild1751 4 роки тому

      @@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

  • @ShortGiant1
    @ShortGiant1 5 років тому +2

    Great video, thanks. Appreciate the table of contents.

  • @MoscleBrog
    @MoscleBrog 11 місяців тому

    people like u save students like us😃

  • @mohannadbayoumi9686
    @mohannadbayoumi9686 4 роки тому +1

    May I ask what the complexity of the non-efficient way you mentioned in the beginning of the video is?

  • @hinocenciopaulo
    @hinocenciopaulo 10 місяців тому

    Thank you so much for this beautiful explanation 🙏

  • @saikatdutta1991
    @saikatdutta1991 5 років тому +1

    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.

    • @BackToBackSWE
      @BackToBackSWE  5 років тому +1

      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

  • @rhiannonsmeby9566
    @rhiannonsmeby9566 3 роки тому

    This video was fireeee I hate recursion but this visualization and explanation really helped

  • @intoeleven
    @intoeleven 4 роки тому +1

    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.

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      If the tree is skewed height checking is O(n)

    • @intoeleven
      @intoeleven 4 роки тому

      @@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/

  • @neghatnazir1668
    @neghatnazir1668 4 роки тому +1

    awesome explination , i love the way you explain things.

  • @shruthiranganatha7333
    @shruthiranganatha7333 4 роки тому +2

    Why add 1 to max(heightOfRightNode, heightOfLeftNode) ?, Wha's the logic here??

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому +1

      Including the node that the call is working on in the height as the calls go up

  • @TheAntloo
    @TheAntloo 4 роки тому +1

    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?

  • @neotong9885
    @neotong9885 5 років тому +1

    really nice job on explaining Balanced Binary Tree!

  • @eliasmoreno4672
    @eliasmoreno4672 4 роки тому +1

    you explained this so well. wow.
    *subscribed :)

  • @malaguna66
    @malaguna66 4 роки тому

    This explanation is so clear so good!

  • @maidul13
    @maidul13 5 років тому +1

    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

    • @BackToBackSWE
      @BackToBackSWE  5 років тому

      I am just simulating the code as it would execute the base case.

  • @khan.mansoor
    @khan.mansoor 3 роки тому

    Great explanation! Do you have a link to the code for this problem that I can refer to?

  • @yuyu-qr7ih
    @yuyu-qr7ih 5 років тому +1

    very detailed explaination brada love u

  • @ashwanigupta4672
    @ashwanigupta4672 3 роки тому

    Finally got an awesome explanation 🏆

  • @PankajKP
    @PankajKP 5 років тому +2

    i hav to pause the video and say GOD to you.... You are GOD!!!!! 😇😇

  • @fantasy9960
    @fantasy9960 2 роки тому

    wow, your teaching is amazing! thanks again!

  • @hikemalliday6007
    @hikemalliday6007 Рік тому

    this dude kills it

  • @qingruxia6312
    @qingruxia6312 3 роки тому

    I love u your videos so much! Thank you so much for your time and work!

  • @sameerpatel3476
    @sameerpatel3476 3 роки тому

    Would a tree be considered balanced tree if the root have only one node at one side ?

  • @kimmyliu5509
    @kimmyliu5509 2 роки тому

    May I ask where is the code? you mentioned it is in description but it is not...

    • @BackToBackSWE
      @BackToBackSWE  2 роки тому

      Do check out backtobackswe.com/platform/content

  • @jgraiver
    @jgraiver 4 роки тому +1

    have you done the code for this anywhere?! loved the video

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      I think so here: github.com/bephrem1/backtobackswe

  • @wentingzhang3097
    @wentingzhang3097 4 роки тому +2

    I'm having trouble finding the code in the description! :(

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      The repository is deprecated - we only maintain backtobackswe.com now.

  • @nortski78
    @nortski78 Рік тому

    Where is the code as mentioned in the video?

    • @BackToBackSWE
      @BackToBackSWE  Рік тому

      Hi, all the codes are available on backtobackswe.com/ 🎉

  • @pushkalkatara2153
    @pushkalkatara2153 5 років тому +1

    Hey, really a great explanation man! It'd be awesome if you could whiteboard the pseudocode too after the explanation.

  • @jf7462
    @jf7462 4 роки тому +1

    Bro, Can you tell me where the code is?

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      We only maintain solutions on backtobackswe.com (paywall)

  • @wahtthepho
    @wahtthepho 3 роки тому

    excellent explanation!! thank you!

  • @超级小棕熊0
    @超级小棕熊0 5 років тому +1

    thank you much ,I totally uderstand how recursion work

  • @MahmoudSayed-hg8rb
    @MahmoudSayed-hg8rb 2 роки тому

    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

  • @wappa6914
    @wappa6914 4 роки тому +1

    Thank you from France !

  • @techzoo1
    @techzoo1 4 роки тому +1

    Your explanation is somehow kinda funny (in a good way)!

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      yeah I was weird when the channel started. no one was watching

  • @souvikbhattacharya9082
    @souvikbhattacharya9082 4 роки тому

    Cant understand why are we adding 1.

  • @pawanacharya997
    @pawanacharya997 4 роки тому +1

    How can someone explain this clearly wow you really helped me..
    thanks

  • @Kellworkie
    @Kellworkie 4 місяці тому

    Amazing teaching!

  • @aishanidatta6293
    @aishanidatta6293 3 роки тому +1

    where can I get the code? I can't see the link

  • @ashishbisht980
    @ashishbisht980 4 роки тому +1

    Bro you are awesome , love from India

  • @pewdiepieschair2693
    @pewdiepieschair2693 3 роки тому

    thanks lad, much appreciated!

  • @cocoarecords
    @cocoarecords 5 років тому +1

    My goto channel for any problem

  • @SreyesSrinivasan
    @SreyesSrinivasan 3 роки тому

    Great explanation, thanks a lot :)

  • @ButhainaMoh
    @ButhainaMoh Рік тому

    oh this takes me to understand this

  • @isabellakang4851
    @isabellakang4851 4 роки тому

    where is the code

  • @AllNaturale11
    @AllNaturale11 Рік тому

    very helpful. thank you!

    • @BackToBackSWE
      @BackToBackSWE  Рік тому +1

      Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=AllNaturale11 🎉

  • @ifelsedeveloper
    @ifelsedeveloper 4 роки тому

    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?

    • @BackToBackSWE
      @BackToBackSWE  4 роки тому

      Yes but that will duplicate subtree measurements

  • @ashwinvarma9349
    @ashwinvarma9349 4 роки тому

    Dude please include in your videos bro that would be of great help!

  • @ajeetworking
    @ajeetworking 3 роки тому +1

    here is the code guys
    pair checkBalanceHeight(Node *root)
    {
    if (root == NULL)
    {
    return {0, true};
    }
    auto ls = checkBalanceHeight(root->left);
    auto rs = checkBalanceHeight(root->right);
    int height = max(ls.first, rs.first) + 1;
    // if the current tree is balanced and it's right and left side tree is balance
    int balanced = (abs(ls.first - rs.first)

  • @mpalanipsbb
    @mpalanipsbb 11 місяців тому

    Best explanation!

  • @notoriousar1606
    @notoriousar1606 4 роки тому +1

    Here is the code
    github.com/bephrem1/backtobackswe/blob/master/Trees%2C%20Binary%20Trees%2C%20%26%20Binary%20Search%20Trees/HeightBalancedBinaryTree/HeightBalancedBinaryTree.java

  • @RedRabbitII
    @RedRabbitII 3 роки тому

    love this! thank you

  • @zackyang123
    @zackyang123 4 роки тому +1

    That 8:40 zoom is gold hahahaha