Data Structures: Trees

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

КОМЕНТАРІ • 366

  • @timgoppelsroeder121
    @timgoppelsroeder121 6 років тому +185

    Finally someone who explains a concept without unnecessarily complicating it thank you

  • @rajsaroj4696
    @rajsaroj4696 5 років тому +412

    2020 but, this playlist saving lives

  • @maazbinmustaqeem
    @maazbinmustaqeem 5 років тому +18

    She just goes through the recursion in a very light way with good animation tool. Loved it. Thanks!

  • @tochinwa1234
    @tochinwa1234 6 років тому +46

    Gayle is a living legend ! Makes data structures and algorithm a doddle. Thanks Gayle. 😘

  • @MegaMoses91
    @MegaMoses91 3 роки тому +6

    This was the best Tree DS explanation I have watched. She’s amazing!

  • @amyp2733
    @amyp2733 5 років тому +44

    Your data structures videos are so helpful! You’re really good at explaining them quickly

  • @flacodoom
    @flacodoom 7 років тому +265

    Very well explained code. Trees always give me problems when asked in tests.

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

    in 2021 and this is still the most simple and well explained version. Thanks Gayle

  • @anaibrahim4361
    @anaibrahim4361 5 років тому +8

    saved me thousands of hours to understand this
    thank you sooo much
    very professional explanation

  • @-0-__-0-
    @-0-__-0- 2 роки тому +1

    I've created a JavaFX App that animates a Binary Tree from an array and this video solved most of my problems. Thank you so much!

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

    This video was so beautifully explained, it's no wonder my lecturer recommended it. Thank you very much for your video.

  • @stewartzayat7526
    @stewartzayat7526 7 років тому +207

    Recursion is such a powerful tool!

    • @Alex-sg6tz
      @Alex-sg6tz 6 років тому +83

      It is until ..... stack overflow

    • @petegeorgopoulos1088
      @petegeorgopoulos1088 6 років тому +55

      be careful tho. A lot of people overuse recursion because they wanna be fancy. But remember, recursion builds a stack in memory and does not release it until it works it's way back to the first call. This could lead to some issues. Most things that people use recursion for can be easily done with a simple loop.

    • @shellgecko
      @shellgecko 6 років тому +7

      only when you have few data otherwise you'll have to use alternatives like dynamic programming

    • @georgievvladimir
      @georgievvladimir 6 років тому +1

      and such a exhausting struggle for the stack

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

      @@shellgecko dafuq are you talking dynamic programming for stack?

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

    Jeez what more could you ask for. Clear, concise, and straight to the point

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

    I would have expected the insert and contains functions to be in a Tree class of some sort, and the node to be an internal implementation operating on a comparable interface. So we can return just the data not the node itself.
    I know it's outside of the scope of this video, but wondering if it's a common practice to put this logic inside of the node class.

  • @motezart2867
    @motezart2867 5 років тому +6

    Best run down of trees I've seen. Code with examples after is very effective.

  • @brendabrownofficial
    @brendabrownofficial 6 років тому +2

    Never knew HackerRank had a youtube channel, the explanations are so good. Thank you for making these!!!

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

      At least you found out 8 months ago, I just found out now

    • @Cfuzion
      @Cfuzion 2 роки тому +2

      @@Wiseman_RSA Atleast u found out 3 years ago..

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

    Very well explained. I found how you visually grouped the "paths" of recursive calls helpful to understand what was happening when "traversing" the tree.

  • @118andrey
    @118andrey 3 роки тому

    Thank you, finally someone who doesn't take an hour to explain a 5 minute topic

  • @tahirrazavi7862
    @tahirrazavi7862 6 років тому +10

    She is literally amazing !

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

    One such algorithm (2:40 of clip) is the AVL Search Tree, where it prevents the skewed linked list Big O performance issue.

  • @dev-skills
    @dev-skills 6 років тому +1

    9:26 - What should be Post Order traversal [8, 5, 15, 10] or [5, 8, 15, 10] ?

    • @dev-skills
      @dev-skills 6 років тому

      Got it should be [8, 5, 15, 10] got a minor typo in my implementation hence was getting the wrong result.

  • @ojazzista
    @ojazzista 2 роки тому +1

    Mind-blowing yet extremely simple recursive implementation!

  • @JoseGarcia-lm3qn
    @JoseGarcia-lm3qn 6 років тому +2

    she is so talented! Learned this right away thanks to her

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

    3 years later and this playlist still getting people jobs😎

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

    2 Questions: method printInOrder() what is System.out.printIn(data) doing? Also in this in-order example.. why after 5 is the next “in-order” number 8? Shouldn’t it be 10?
    I understand recursively we’re traversing to the Left most depth node in the binary tree ( up until left == null ) - but I’m confused how we’re printing from that point forward.

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

      Similar question here. Once it's on the bottom of the left side of the tree, on either left or right node, how does it jump back up to root node?

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

    Really crisp , clear and easy explanation. DS became so easy to grasp the way you explained.

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

    For the insertion. You have to Check if there’s a root node first of, I think. If data == null, then value = data;

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

      it is called as,
      public static void main(String[] args) {
      //Say you have a tree with root node being "root"
      int value = 6;
      if(root!=null) {
      root.insert(value);
      }
      }

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

    In the insert method, what if the tree is empty, how it would insert the first node, since the code says left or right

  • @kicksomeup6998
    @kicksomeup6998 3 роки тому +8

    Thanks for the video. But IMO there is an issue with how the code is written since these methods are operations on the tree data structure, not the node data structure, hence they should be located inside the respective ADT. Apart from that, the code looks great and is easy to understand. Great work!

    • @Anon-jz7iw
      @Anon-jz7iw Рік тому +1

      That's what I thought too. It really confused me in the beginning till I realized it's not really a code for a node but for a binary search tree.

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

      @kicksomeup6998 you mean that each individual node does not contain a node data instance variable? Or that the contains() method is not written as an instance non static method within the node class?

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

    In the insert method it would not be val = data

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

    Wow, this was precise, easy to follow and I feel I understood what is going on
    Really great stuff!

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

    I think you should have implemented contains method in the Binary Tree class instead of the Node class

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

    This is gold!! Everything made sense now!

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

    I love the presentation of code alongside diagrams as im a visual learner, really appreciate it.

  • @granturismoautos
    @granturismoautos 7 років тому +46

    this is AMAZING!! Well explained!

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

    Very excellent explanation, clearest one I’ve ever heard. Deleting needs its own video, so I understand why you decided not to include it. On programming tests, I’m always like “can I not write out all the recursion methods? I hate writing all the if statements... we both know what we are talking about, this is a binary search tree ok?” haha.

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

    I watched this video and programmed binary tree in python totally it took me 30 mins... Professor could not explain in whole semester: D

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

    0:40 Binary Search Tree
    3:08 Types of traversal

  • @Phoenix84118
    @Phoenix84118 6 років тому +26

    Finally, someone who write 5 the same way I do!

  • @36nibs
    @36nibs 3 роки тому

    Are use the same technique to schedule my priorities and tasks throughout the day.

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

    This was a really clear explanation. Thank you!

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

    Did she just pull a recursion and I understood it? Damn she's great!

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

    Great explanation. My only question is how to implement it such that the node can contain an arbitrary (but homogeneous) data type?

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

    Good stuff! Makes me feel dumb when the teacher says "Let's implement this. It's really simple."

  • @rishabh3952
    @rishabh3952 7 років тому +4

    short and on point that's wat I wanted.saved my time! thanks.

  • @ijustsawthat
    @ijustsawthat 7 місяців тому

    2:46 Candidate: these algorithms can be very complicated, so we are not going into details here.
    Interviewer: Understandable, have a good day.

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

    There must be an implementation of delete function in this video, it will add more value to it.

  • @bik8353
    @bik8353 6 років тому

    Thank you for this vivid walkthrough of the code. This is one of the best of this kind

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

    Really Great Video and Explanations within short minutes which we can understand the concept. Kudos!! Team.

  • @tan8067
    @tan8067 5 років тому +6

    Wow! Thank you so much for explaining this, I get it now. Now I just have to practice it.

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

    This was such an easy to understand video. Does anyone know if Gayle Laakmann McDowell has her own channel?

  • @mfaani
    @mfaani 6 років тому +1

    I was confused as to how 10 gets printed before 5,8.
    But it's more like, if root has something then do printInOrder of left & 'AFTER' left.printInOrder (which is recursive in itself). print the node itself. So basically the ENTIRE tree on the left of every node gets printed first...Then the root of every subtree, then then the right and finally the ENTIRE subtree of the right

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

    Thank you very madam. you have explained the Basics of tree traversal very nicely in a simple way..

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

    Thank you so much for the explanation!

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

    WOW.... she explained it very well. Once you understand it... it's basically like elementary.

  • @H3000-v7i
    @H3000-v7i 6 років тому +1

    I think this is cleaner... but is it better/worse? (Its C++, if any wonder)
    bool contains(int value){
    if(this == nullptr)
    return false;
    else if(value == data)
    return true;
    else if(valuecontains(value);
    else if(value>data)
    return right->contains(value);
    return false;
    }

  • @elijaheinstein160
    @elijaheinstein160 7 років тому +6

    Is the insert() method inside Node class ?

    • @Nicole-px3ll
      @Nicole-px3ll 6 років тому

      yes

    • @dev-skills
      @dev-skills 6 років тому +2

      Another way would be to create a Node class as an inner class of Tree class and provide insert, delete, traversal methods within Tree class instead of Node class. I found this approach better from OO Design perspective but slightly more complex and difficult to present during a coding interview.

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

    I recently got an assignment of a BST with satellite information on each node. I haven't found anywhere any information about this. Would you please do one about this. I am taking an algorithms class.

  • @JustSkillGG
    @JustSkillGG 6 років тому

    Its a very nice and simple way to do all that stuff , but what about the destructor? How would you do it ?

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

    Very informative and straight-forward video, thank you!

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

    More than amazing. Such a simple explanation. Well taught. Thanks HackerRank...

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

    Honestly, after watching this video I got confused. I am sure that this code works fine, but why is there no Binary Tree structure being created? All the functions which ideally should be written for a BST data structure are written for a node. So if I wanted to construct a BST, do I create a Node object??

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

    You made it very easy to understand. How simple it is and I always fear with the name trees.

  • @JoseAlvarez-dl3hm
    @JoseAlvarez-dl3hm 5 років тому +1

    Very nice little lecture, but I cannot figure it out which would be an example of a good real developer scenario in which a tree would be the more efficient way.

  • @virginman101
    @virginman101 8 років тому +1

    is the contain(value) basically functionception ?

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

    I followed her steps on the printInOrder() method up until the 8, but then when she said 10 prints next, and then 15, she really lost me, I just don't see how it worked with the recursion. Can anyone help break it down into steps?

    • @thabznss3065
      @thabznss3065 7 років тому +6

      So basically, what you are doing here is looking if left exists, because presumably when it doesn't, you are at the top most element, which in this case, will be the smallest. If you write out the code and step through in a debugger, we use the last inserted left. When we see that this left isn't null, we call the function recursively from that instance of left, which it has a left and data property on its node as well. This process repeats until you reach the top, in which left is null, so you print the data for the first time. Once it reaches the topmost element, it then has to go back down the call stack, to call the System.out.print.ln() method for the data for each predecessor. Then you work the right side in a similar manner with recursion and the call stack.

    • @kenocvr
      @kenocvr 6 років тому +1

      It's the order of the call stack. Remember 10 is the root node and still hasn't "resolved" just because we've traversed down the left side. The stack will resolve in reverse order.

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

    i understand your teachings better than my prof. nice video!💜

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

    I have a doubt here on insert. I didn't understand how the first node will get inserted, i didn't see any check in code whether data is null if it is first element. Correct me if I didn't understand well

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

    How come there was no class bst? Dont we want to keep a reference to the root? Also missing deletion function.

  • @SuperOneWinged
    @SuperOneWinged 8 років тому +5

    I love your videos so much, keep it up, you are one of the best

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

    what if the inset value is same as the root? make an assumption that we go left in this case?

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

    Anyone know if binary trees usually use recursive for their functionalities? Still learning about data structures / algorithms, but doesn't it add up in stack calls depending on the size?

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

      you can use both recursive and iterative

  • @experiment0003
    @experiment0003 2 роки тому +1

    is this pseudocode? Because this seems wrong. For example, how does line 9 access data in the Node subclass?

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

      There seems to be some confusion here. If by subclass, you mean the constructor, that's not what line 9 is accessing. It's accessing the data variable on line 3. In this case, the data variable has class wide scope, allowing it to be accessed within the class. Look up the "understanding class members" tutorial on from oracle for Java, as well as variable scope. And constructors are not the same thing as a subclass. A subclass is simply a class that inherits from another class.
      This could have also confused you, as the data class variable has the same name as the data passed into the constructor. "This(dot)data" is the class wide variable, and data is the variable passed into the constructor when creating an instance of the class. There are quite a few things I didn't mention, as it would be too long, but I'm sure you can look it up. Happy coding!

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

      @@trenvert123 Thank you very much for your thorough explanation! After looking at it again, I see where my confusion was. I see that int data on line 3 is a global variable that can be accessed anywhere within the Node class. At the time I was relatively new to the Trees data structure. I'm still learning though. Once again, thank you so much!

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

    Very clear explanation and simple understandable code, Thanks a lot

  • @LeBronJames-ns6to
    @LeBronJames-ns6to 7 років тому

    Can you give examples of a PreOrder and PostOrder Traversal? Even tho I prefer InOrder

  • @mostdeathgaming
    @mostdeathgaming 6 років тому

    What is the significance of the contains function in the above program??

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

    I hope you can post a video on how to build a relatively balanced tree. With the example on this video, all the weight goes to the right side of tree. Like you said in the video is not very efficient.

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

    it's really helpful you are like saving lives appreciate it. thanks ma'am.

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

    She explained this 100x better than my professor could

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

    Are these trees how people do those path finding algorithms?

  • @ashishmishra672
    @ashishmishra672 7 років тому

    Wow. The way you explained it, beautiful!

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

    Such an amazing explanation!!! Thanks for your video

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

    What ways are there to turn more complex trees into binary trees?

  • @muktadirkhan6674
    @muktadirkhan6674 5 років тому +6

    She always have to bash that she is the author of Cracking the Coding Interview. I know it woman. I have watched tons of your videos.
    Edit: I love your videos

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

      It is the first time I watch her, so I didn’t know that...

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

    Excellent explanation !! I can tell you, you have done excellent work, simple clear, and concise well done !! and thank you !!

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

    ```
    public void insert(int value) {
    if(value 10``` after that? (I'll got duplicate of 10?)

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

      Yep. There isn't an agreed definition of how a Binary Tree should handle duplicates. Put it in the left, put it in the right, ignore or maintain a counter of duplicates in the node

  • @realworldcodingapplications

    wow this was pretty simple explanation and easy to understan thanks

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

    so binary trees are like the chemical equations? How to balanced them and that?

  • @jgshanth
    @jgshanth 6 років тому +33

    "lets add a constructor to make our lives easier" god this developer life

    • @itsajin
      @itsajin 6 років тому +4

      if only the constructor initialised the left and right to null

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

      itsajin why? Node is a reference type....it’ll be implicitly null....

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

    When it has 5 and it takes 5-1=4 and again calls the function, then does the previous value 5 is stored in memory till it reaches 1?

  • @rasheedlewis1
    @rasheedlewis1 2 місяці тому

    What about balancing the tree?

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

    Ohh my God what a simple expression u are Wonderfull teacher

  • @PriyankaSingh-vm4kv
    @PriyankaSingh-vm4kv 4 роки тому

    Amazing explanation!! Can you make more videos on data structures covering all topics plz

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

    Fantastic breakdown. You are the truth.

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

    You are phenomenal... Loved your video.💕💕

  • @eduardmart1237
    @eduardmart1237 6 років тому

    How to do it witout recursion?
    In a large tree it can lead to stack overflow...

    • @ericzell4138
      @ericzell4138 6 років тому

      For iterative depth first search, use a stack: (Ruby code below)
      def depth_first_iterative(node)
      stack = Stack.new(node)
      while !stack.is_empty?
      node = stack.pop
      puts node.value
      stack.push(node.right_child) if node.right_child
      stack.push(node.left_child) if node.left_child
      end
      end

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

    is it my idea or 8 should be printed before the 5?

  • @75hilmar
    @75hilmar 3 роки тому

    Just what I needed right now.

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

    omg trees are this simple? fantastic explanation that too in this much short time.

  • @upgames1313
    @upgames1313 6 років тому +3

    this was so well explained and clear! thank you!