Binary Trees in Python: Introduction and Traversal Algorithms

alright so in this video we're going to be going over binary trees so we're going to be covering briefly the binary tree data structure and how it's defined and then we're going to be going over an implementation of a binary tree in Python so for definition a binary tree is a tree data structure in which each node has at most two children which are referred to as the left child and right child so here's an example image of a binary tree and each of these circles here these are what we call the nodes of the tree so just like in a linked list we had the nodes of a linked list stored some type of data so this could be an integer it could be a string it could be a pointer to another data structure in this case these nodes contain integers so unlike linked lists where the node pointed to the next node in the list a binary tree has two pointers that point to its children so every node in this tree will have it in most two children and this makes traversing such a data structure interesting and a little bit more varied than you would a linked list and we'll get to that later in this video so a bit more terminology about a binary tree we refer to this top node here as the root so in this case the node that contains the element 2 this is the root of the tree and then the left and right children of this root node are the nodes containing 7 and 5 respectively so they are the left and right children of 2 so if we consider this node here this node that contains a 7 it also has at most 2 children so it's left and right children are the nodes containing 2 and 6 and we say that 7 is a parent node with respect to 2 and 6 so 7 this node here containing 7 is the parent of the nodes containing 2 and 6 and likewise this node here containing 2 is the parent of 7 and 5 so as we go up the tree we go up kind of the family tree if you like so - here is the grandchild of 2 so 2 is kind of the grandparents parents and child and you can keep going up the tree we just refer to 2 as an ancestor of of 2 down here so a few more pieces of terminology here we refer to the nodes the very bottom of the tree as the leaves so the root is up here and the leaves are the very bottom we can refer to the depth of the tree so if we start at the top here at the root and we keep going down we keep it count at how deep how many levels we've traversed down so for instance this root here is at level let's say you can start at zero or one and then as you go down these nodes here are at the next levels they're at level let's say one two and then as we go down further these nodes 2 6 and 9 are the next level down so they're at depth 3 and then these nodes here these leaves they're a depth 4 so 1 2 3 4 depth 4 count from the bottom to the top and that will give us the height so if the leaves are the bottom level let's say height level 1 then we can go up to the next level up here these nodes are at level 2 level 3 and then level 4 so this tree has height 4 so there's different types of binary trees and this list is not complete there's plenty of other types of binary trees you can consider but we can consider the two that we're just going to mention on this slide so a complete binary tree so this is an example of a complete binary tree and a complete binary tree is one where every level except possibly the last is completely filled in all nodes in the last level are as far left as possible so this level is completely full you can only have one node here this level is completely full this has this node has the maximum amount of children both of these nodes they have the maximum amount of children as well and then all the nodes in the last level with the leaves there it's not full so we have here in the definition that possibly the last level is not completely filled and also the last level nodes the leaves are pushed to the far left so this node is as far left as you can go so in order for this to maintain the property of being a complete binary tree the next node that we would insert would have to be the right child of this node 4 and so on and so forth so a full binary tree is sometimes referred to as a proper or plain binary tree and this is one where every single node has either 0 or 2 children so every node in the tree has 2 children except for the leaves which have 0 children so this is full tree every every like a space in this tree is being taken advantage of so this is a full binary tree so with that we have enough terminology and information to start defining the data structure of a binary tree and we're going to see a lot of overlap with what we saw we define the data structure of a linked list so I I would recommend that if you have not gone over that series or if you need to brush up on linked lists especially how they're defined let's say in Python to get a flavor of how we're going to extend on that I would encourage you to go over and check out that series of videos maybe the first couple of videos just to get a flavor of how one would define such a data structure and once you feel comfortable with that we'll go over to the terminal and we'll start to define a binary tree alright so let's go ahead and code up our binary tree data structure in order to do that we'll first define a node class so this is going to be really similar to what we did when we defined the linked list data structure where we had a node class as well for the nodes in the linked list so we'll say class node and then let's go ahead and define the constructor for this class so we'll say def in it and just like for the constructor of the know class for a linked list it's going to take self as it's a member of this class and also value so this is the type of value we wish to store in this particular node so we'll set the class variable value equal to what's passed in here and then unlike a linked list where we had the class variable of next set equal to none we're going to have left and right equal to none so next were the that was the pointer that points to the next node in the linked list here we're going to have two other pointers left and right which are going to point to the left and right children of the given node respectively so we'll say self dot left is equal to initially none and then self dot right is equal to none so pretty similar to what we saw in the linked list class with the exception of those two last variables let's go ahead and define our binary tree class so here what we're gonna do is we're also going to define our constructor so it'll take self is it's a member of the class and also root as that will define the tree so we'll say self dot root will be equal to a node of root so what I'm doing here is I'm assuming that a value like let's say string or an integer will be passed in to define the binary tree and then what I'm doing is I'm setting the class variable self dot root equal to a node of that so we're converting what where data is passed in we're storing that into a node and we're setting that as the root of our tree here so that's pretty much all we need to get started we can actually start filling this tree up although we won't be able to print anything out at the moment so we can say tree dot root is equal to let's say or actually first we need to define a binary tree objects we'll say let's say binary tree or will even be a bit more concise here will say tree is equal to binary tree and in in this argument we're going to put in the initial value of the root so we'll put we'll go ahead and put one in there so we have a tree object now and what we can do is we can start filling in the the nodes the left and right children of this particular root so what we can do is we can say tree dot root that left is equal to node of two so what this is going to do is it's going to we're gonna start off with a root node here so one is the root of the tree and then what we're doing is we're creating we're creating let's see if I can get the right slash so we're creating a left child of this root node and we're sending the value of that equal to two so we can also create a right child of the root node we could say free dot root dot right is equal to node oops didn't mean to do that is equal to node of three so here what we can do is we're going to define the right child to this thing we're going to set that equal to a value of three and we can keep going so we can say tree root dot left dot left is equal to node let's say if for so what that's going to do is it's going to define let's get some more space here move this over here move this over here a bit more space there so let's see let's just space these apart appropriately so two is left child of the root one and then two is going to have a child now so two is going to have a child a left child let's see here move this down here to is going to have a left child of four and then we can also define let's say tree dot root dot left dot right is equal to no two five so what I'm doing here is I'm saying that tree dot root dot left so here we're here dot right so right will be the right node of two so we can set that equal to a value of five like that and we can continue in this way so if we want to insert nodes in a tree in this way this is kind of what this particular tree is going to look like in this case so we can go ahead and fill this in a little bit more so I've gone ahead and filled in the tree to be a little bit more complete here adding two more nodes of this node right here so I've added a left child and right child for this node here so just filled in the tree a little bit more not necessary but it gives us a little more data to play with so now what we want to do is we want to find some way to actually go through the tree to traverse it in some way and to actually print out the elements stored at the respective nodes so remember for a linked list there was pretty much just one way to traverse it there was a linear way we just started from the front of the list and then we just moved progressively through the list sometimes you might do something fancy with maybe two pointers where you have one pointer that kind of goes a few few nodes ahead of the first one and then you kind of traverse it using two pointers but you still traverse the list in a linear fashion so here with a tree since we have a different type of structure we're going to think about the different types of ways one can traverse a tree and we're going to be going over kind of the most basic ways in which one can do that focusing first on something called depth-first search and there's three different flavors that will be covering which are pre-order in-order and post-order traversal so we'll be covering those and then we'll be seeing how we can implement each of those traversals in python and if we consider a recursive way of defining each of those traversals then once you define one it's pretty straightforward to define the remaining two so we'll cover that next so back to the slides as we mentioned before a tree traversal for binary trees here will be a process of visiting checking and/or updating each node in a structure exactly once so as mentioned before unlike a link list or any other 1 dimensional data structure like an array which are traversed in a linear manner trees can be traversed in a number of different ways and we're going to be going over some of those so we're going to be focusing first on depth-first search and those three different ways that we mentioned post pre and inorder traversal will be flavors of depth-first search and as I mentioned I guess this is just kind of a reiteration of what I mentioned before there are a few common ways to do so and the depth-first search order that will be considering are these three different types of ordering traversal schemes so let's first cover pre order traversal so what we do here is we start at the root we check if the root is empty and then we just kind of go down through the left subtree and then we go back up and then we consider the right subtree so let's actually just follow kind of how pre order traversal goes so we start here we started at the root and we print out the element of the root so that's going to give us our first output of the pre-order traversal here this F so then we move down the left subtree so we're here we're at B and so we print out the element at B that gives us a second element here and so then we check if the left node of this one is not no it's not so we follow it here and then we print out the element at that element at that node which is a and then we check the left we check if there's a left node of the one that we're on here so there's no left node here so that's null so what we do is we go back up to this node here this B and then we check the right now so we moved down here to D this node here with thee we print that out so now we're a D and then we follow the left subtree so we start here we're here now at D we follow left we see that we're at C now print that out we check if there's a left node here to see there's not its null so we move back up the C we move back up here to D and then we check the right subtree of D so we move down here to e print that out check left nothing check right nothing move up move back up move back up to the root we've already covered that so now we move to the right subtree so we move down to the right subtree where a G we print that out there we check if there's a left node there's nothing there so we don't do anything there so we check if there's a right node there is and that is I so we print out I to the screen and then we check if there's left node there is let's H we go ahead and print that out we check if there's a left node there's no left node right node no right node go back up here to I check if there's a right node there's nothing so then we move back up move back up and we're done so we've got our pre-order traversal there so what we're going to do is we're going to code this up and then we're going to go back to cover the other two traversal algorithms and those are going to be very similar in terms of implementation from an from a recursive standpoint and once we understand this one implementing the other two should be pretty straightforward all right so now we're back here in the code let's go ahead and create a pre-order print function which will be responsible for printing out the nodes in a pre-order fashion so we'll say pre-order prints it'll take self since it's a member of the class start this is the node that's going to be updated on every single recursive call of this function and then traversal this is going to be a string that will print out to the screen and we're going to essentially update this on every single recursive call and then we're going to return this so we at the end of the day once we've done once we're done finishing this function we're going to have just one string of elements which are going to correspond to the elements printed out in whatever traversal we specify in this case the pre-order traversal so hopefully that will become clear as we implement it so again just to kind of clarify the order in which pre-order goes it starts off with the route it considers the left subtree and then it considers the right subtree that's kind of the flavor of pre-order traversal so we're gonna check if the node that we're given in this recursive call is none so if it's not none then what we're gonna do is we're going to say traversal again this is just going to be a string that will constantly update on every call so we'll say traversal plus equals string start value and then what we're going to do just to kind of separate the output is just add this - so on every recursive call to this function as long as this know doesn't know what we'll do is we'll say okay print out the value concatenate that to this traversal string and then print out that value and then just append on a little dash to show that we're kind of chaining these outputs together so it just formats it a little bit nicer and then what we're going to do is we're going to say traversal is equal to self that pre-order print so we're recursively calling this function and then we're going to call it with the left subtree right so the left child of the node that we're given in this recursive call and then we're going to pass it in the traversal string that we were going to continue updating on each recursive call and then once that finishes for the left subtree we're going to consider the right so we're going to say traversal is equal to self pre-order prints start dot rights and then we're also passed the traversal as that will get updated on each recursive call and then once that is completed we'll return traversal so let's go ahead and create kind of a helper function which will be called prints and that will be responsible for let's call it print tree this will be responsible for printing out the tree and we'll specify what type of traversal algorithm we want to print the tree out in so we'll say print tree oops print tree so self and then we'll specify a parameter called traversal type so here we'll just be giving this function a string so for instance maybe we want to print a pre-order post or door in order in other videos we'll see iterative flavors of these algorithms we might want to print them out in other types of traversal algorithms so we'll just go ahead and say the traversal type is a string parameter that we will specify to a call to this function so we'll say if traversal type is equal to let's say pre-order then what we'll do is we'll call the pre-order function so we'll say return self dot pre-order print and then we'll pass it in the root of the tree because that's where we're gonna start the pre-order traversal and then we'll initially pass it in an empty string so this empty string on the first recursive call will be nothing and as it goes through this function it will continually be updated with the values stored at each of the nodes as we follow this traversal so that's pretty much all we need for the pre-order traversal function so let's go ahead and go down here and we'll say tree print tree and then we'll specify the traversal type again the type that we specified is pre-order and then maybe what I should do up here is I should also say if otherwise let's say we feed in a traversal type that's not supported we'll say you know Prince traversal type let's say string of whatever you fed in traversal type is not supported so just in case someone feeds feeds in some argument here that's not supported for this particular traversal type so we'll just return false there okay so that was just a bit of error checking I suppose so what we're gonna do here is we're going to call this printer e function and we're going to specify that we want to print out the nodes in pre-order so let's go ahead and save this and what we'll do is we'll clear the terminal and then we'll say Python binary tree pi and I think I don't see anything because I need to print what is returned from this function that would explain that so here we see that the pre-order traversal is one two four five three six seven eight so let me just copy this and we'll step through the tree to make sure that actually makes sense so let's go up here I'm just going to put that in a comment in a comments let's see let's do here right so that is the pre-order traversal so again we started the route that makes sense so we print out the element at the root so that's what we do here for the first element there then we follow the left subtree so the left subtree we've got two that makes sense we follow the left subtree again we got four we check if there's any left node here there's not so we move up we move up and then we check if there's a right subtree here there is so we have five by the way when i was back down here we check if there's a left subtree there's not and then we check if there's a right subtree there's not so we moved back up to here just to clarify check the right child of two so that's five that gives us five here check left nothing check right nothing move up move up and then move to the right subtree so that gives us three and then we check the left that's six check the right well check the left here six check left check right nothing nothing go back up to three check we got seven and then it looks like I just forgot to add in in this figure here this 8 so I'm just gonna go ahead and if I was to remove this 8 here and remove this one right there this would be accurate with this comments here I just forgot to reflect that in the in the figure here in the commented figure so if we went ahead and just ran this again just to be clear the 8 is no longer there I just wanted to accurately represent what is represented in this comment figure here so that seems to have given us the pre order traversal of the tree so that seems to have worked as expected good so let's go over the other traversal algorithm so post order and in order and they're going to be very similar to what we've seen so far ok so just like we had the pre order traversal we have the inorder traversal here and we're going to be stepping through it in a very similar way so pre order was we've considered the routes than the left and then the right subtree so in inorder we're going to be considering the left the route and the right so it's kind of a natural name for such a traversal because we're kind of reading the tree from left to right right and in order traversal left routes and then right so if you actually just read off the nodes here from left to right a b c d e f g h i that is the output of what would be an inorder traversal you're kind of reading the notes from the left to the right that's going to give us the output of this inorder traversal so let's step through it in the same way here we start off with the root and then basically what we do is we go down as far as we can to the left so we start off here can we go to the left yes ok we go here can we go further to the left yes so we're here can we go further to the left still no we can't so go ahead and print out a so we prints out a we move back up we print out B and then let's try and go down as far as we can here so we go down can we go down further than here yes we can can we go down further than here to the left no we can't so we print out C we move back up prints out deep and now let's see how far down the right we can go so we go down here to e can we go to the left no can we go to the right no so go ahead and print out e so he prints out e move up move up move up and then at the root--so prints out the roots so again left to root right so prints out the root and then now we're going to traverse the right subtree so move to the right prints out G and then move to the right again can right so you're back up at the root you print that out and then you consider the right subtree so you move to the right and then you check and you go to left no you can't so you go up here you print out G go to the right here and then what you do is you say can you go to the left yes you can so you're here go to the left no you can't print out h go back up can you go to the right no you can't okay so prints out I and then move back up and back up and that is the inorder traversal so that's pretty much it for that so now what we can do is we can implement this again it's got kind of a natural recursive flavor to the way that you would think about how to implement this especially in a binary tree like a data structure so let's go ahead and go back to the code and implement an implementation of inorder traversal all right so now we're back here in the code so let's go ahead and create another function which is going to be similar to pre-order prints but it's going to be called in order prints so we'll call this inorder print so it just will take the exact same parameters self starts and traversal and then in this case what we have again is we have left root right so that's kind of the way in which the nodes are going to be right off in order traversal and we'll have a very similar start here so we'll say if start so if the start node is not known what we'll do is we'll consider first the left subtree so we'll say traversal is equal to self dot inorder print and then we'll say started out left because we're considering the left and then we'll feed in that traversal this traversal is going to be the string just like it was in the pre-order prints that we're going to be continually updating on every single recursive call so once we've considered the left subtree go ahead and print out the route so we'll say traversal plus equal string start value and then we'll say give it a little bit of a dash there for nice formatting and then what we'll do is we'll consider the right subtree so we'll say traversal is equal to self dot in order Prinze and then we'll say start outright traversal okay so that's what we need there and then we're also going to return traversal let's go back up to a print tree function here and we'll add some support for the inorder traversal so we'll say else if traversal type is equal to in order then what we'll do is we'll return self dot in order prints and we'll pass at the root of the tree and then again just like we did before just an empty string to start us off for the traversal output so we've got that let's move on down here and if we've got inorder traversal what we should see is we should see four to five one six three seven so again it's an inorder traversal left subtree first then the root then the right subtree so what we should see is we should see four to five one six three and seven so let's go ahead and run that to verify that is what we see I'm going to comment out this line here for the preorder traversal and then I'm going to go over here and type in in order so we'll write that and we'll give that a run so indeed we see four to five one six three seven so that is the inorder output of the nodes for an inorder traversal so the lesson is when you define these recursively look how similar this pre-order and inorder definitions are and indeed for postorder it's going to be a very similar type of extension from these two functions in a post order you can probably imagine we've considered here the routes left right left right or left root right and now for the post order I'm just going to go ahead and define the prototype because it's going to be very similar to what we've seen so far let me say post order prints again it's going to take the same type of information the same type of arguments that the previous two functions did and then here what we're going to do is we're going to start at the right oh sorry not the right we're going to start at the left then we're gonna move to the right and then we're gonna move finally to the root at the very end so I'm just going to go ahead and copy this here since this is going to be nearly identical to the post order traversal of what we want here so instead of these lines being in this order since we want the route at the end we'll take this move it down to the third line here so we've processed the left subtree we've processed the right subtree and then the route so this is going to be the post order traversal for this particular tree so we'll go ahead and see how that looks like so again what we're doing here is we're considering the left the right and then the route so it should be 4 2 5 6 3 7 1 so let's go up and create a helper function here for the or to add some support for the prints free function so we'll say else if traversal type if that's equal to post order we're going to return self dot post order prints of tree dot root and then again an empty string just because that's what we want to start off with so let's go ahead and run that so again just like before I'm going to comment this out and then I'm going to take this modify slightly and put in post order here so I'm just going to post order write that let's give it a run so we see 4 2 5 6 3 7 1 4 2 5 6 3 7 1 so is the post order traversal of the tree so that pretty much does it for this video so just to review we went over the binary tree data structure and then we went over the 3 different I guess most popular or well known types of traversals for a binary tree so pre-order in-order and post-order so these are all flavors of depth-first search and we'll be continuing to investigate this data structure in further videos in this playlist and for instance thinking about how to implement these functions not recursively but also iteratively and just other things that we can ask other questions that we can ask about a binary tree data structure and maybe what it can be useful for so thanks again for watching the code is always will be available on my github page and the link for that will be in the description to this video if you have any questions or comments or clarifications or anything like that do not hesitate to leave them in the comment section below and thanks again for watching and have a great day

Channel: LucidProgramming

Views: 129,597

Rating: 4.9335132 out of 5

Keywords: binary trees python, data structures in python, python data structures, binary tree traversal python, python binary tree traversal, binary tree python lesson, python binary tree tutorial, binary tree preorder traversal, binary tree inorder traversal, binary tree postorder traversal, preorder traversal python, inorder traversal python, postorder traversal python, lucidprogramming

Id: 6oL-0TdVy28

Length: 28min 40sec (1720 seconds)

Published: Mon Mar 12 2018