Data Structures: Trees

Key Takeaways

hi I'm Gail Locke McDowell author of Kraft encoding interview in this video I'm going to cover trees a tree is best thought of in this sort of picture you have a root node at the very top and it has child notes and each of those child notes they have child nodes themselves and so on and so on very often when are talking about trees we talked about binary trees a binary tree means that each node has no more than two child nodes that is that each node has a left node and a right node of course one or one or both of those could also be null very often when we're talking about binary trees we actually want to talk about binary search trees a binary search tree is a binary tree which fulfills asa civic ordering property so on any subtree the left nodes are less than the root node which is less than all of the right notes this ordering property makes finding a node very very fast because we have a pretty good idea of where it would be so suppose we're looking for 17 in this tree we can say okay is 17 bigger or smaller than the right than the root node well it's bigger than the root node so let's go to the right now is it bigger or smaller than that next node there well it's smaller than that node so it must be on the left of it and so very very quickly we can start to zoom in on where that node will be because it each operation we've chopped off hopefully about half of the nodes and we do that over and over again and very very quickly we find the node we're looking for so makes finds very very fast but how do those elements get in there in the first place well let's talk about how inserts work inserts work much like finding an element works we start with some element want to insert like say 19 and we say is it bigger or smaller than the root well it's bigger so let's go to the right now is it bigger or smaller than that next note it's smaller so let's go to the left I'm going to this over and over again until we get to an empty spot or no node and then we say okay that's where we should insert our new element now the one problem here is that if we get elements in a particular order we could get really imbalanced suppose we have a new binary search tree and we just follow the properties of insertion so we insert one and then two to its right and then three to its right and four to its right we're going to get this data structure that looks less like a tree and more like a long list and then inserts and finds will no longer be so fast there are some algorithms that can ensure that our tree stays balanced that is that roughly the same number of nodes will be on the left side of the subtree and on the right these algorithms get pretty complicated so we're not going to go into the details here but it's worth knowing that they're built into a lot of programming languages and in a lot of cases and interview questions you'll just assume that you have a balanced tree the last operation to talk about is traversing or walking through a tree so there's three common ways we walk through tree we can do an inorder traversal a pre-order traversal or a post order traversal a pre-order traversal means that you visit the route first and then you visit its left nodes and it's right notes in an inorder traversal you visit the left notes first then the current node and then you go to the right nodes in a post or adverse 'el the root node comes up last so you visit the left nodes than the right nodes then the current root node typically in binary search trees we want to do inert reversals because that actually allows the nodes to be printed in order so for example on this tree here it was just a 1 a 2 and a 3 the nodes in an in order traversal will actually print it out in the order one and two and three so typically we'll see in art reversals now that we've covered the basic operations let's take a look at the code for binary search tree to implement a binary search tree we'll need a class node that has pointers to the left node and the right node and then some sort of data presumably and I'm going to give ourselves a constructor just to make our lives a little bit easier okay so the first method I'm going to add is an insert method and this is going to take in I'm going to call it value here this is going to take in a node there tip taken a node value and look to the left and the right to see where we want to insert it so first if value is less than or equal to the actual data of our node then we should insert it on the left side if there is no left node yet then this becomes my new node otherwise then I ask my left to insert it and I push that down the recursion stack and then otherwise if value is bigger than data then myself then it should be inserted on the right side and so if there is no right node put this as my right node otherwise ask my right to insert it okay so that's the basics of insert okay so let's walk through this code on an example so we have the simple tree and we want to insert the value eight so we call ten insert of eight and eight is smaller than ten so we go to the left and call left insert of eight so five dot insert of eight eight is bigger than five so we go and we don't have a right child and so we set 5s right child equal to eight the next method I'll do is find so find is going to operate recursively just like insert in fact it'll be somewhat similar in a lot of ways and it's going to want to return a boolean I'm actually going to call this contains because we're not really finding the nodes much as checking if the tree contains it okay so first of all if I'm their return true otherwise if value is smaller than data that it should be on the left side if there is no left node then I know the answer is false otherwise if there is a left node go ask my left node what the answers okay now I do the same thing on the right if welcome to student else if right is null if there is no right node the answer is false otherwise go ask my right child and return its answer all right so that's it recursive plantation of contains so let's walk through this function imagining we're trying to find the value eight that we adjust insert it so we call ten that contains of eight eight is smaller than ten so go to the left and then we do five dot contains of eight five is smaller than eight and so we go to the right and then of course we see that eight in fact equals eight and so we return true all the way up the stack final method that'll implement is a inorder traversal typically I'm going to print all of the nodes in the tree so I just call this print in order and this is actually very simple first if my if I have a left child then I do my in order to running first of my left child then I print my own data and then same thing Li right if right is not null then I do right dot print in order so remember the inorder traversal z' do the left child myself and then my right child so that's exactly what the code here does so that's how we do an inorder printing let's walk through what this code does so we're going to first call ten dot print and order ten is going to say left print and order first that's a very first thing that's going to happen then we're going to print the route and then it's going to say write dot print in order so we're going to recurse down and five so we can get five dot print in order five is going to say okay print got nothing on the left to print so print me next and then call write dot print in order where eight will get printed and then we're going to go back up to ten and ten is going to get printed and then we're going to go and go down to the right in that third step and print 15 so that's how an inorder traversal works if we want to do a pre or post order traversal we do a very very similar thing to send a slightly different order a pre order traversal means that the route gets printed first so we'd print the route then print the left sub-tree then print the right in a post order traversal the route gets printed last so we'd print the left then print the right and then we print the root note so it's a pretty natural translation of the algorithmic concepts a lot of times in interviews people get kind of intimidated by the idea of implanting a binary search tree they just assume it's something really challenging but if you understand the concept pretty well you can just take that and just translate it fairly directly into the code just be really careful about the null pointer checks so now that we've gone through the basic operations while you try out these concepts on a new problem good luck