Beginner tree algorithms | Graph Theory

Key Takeaways

[Music] [Music] hello and welcome my name is William and in today's video we're going to look at some simple tree algorithms this video is aimed at all you beginners just starting out who are still learning how to write code and especially learning to write recursive code we're going to have a look at two problems and these are the types of problems which you might encounter as a warm-up question during a job interview all right let's get started with our first problem for this problem we need to find the sum of all the leaf node values in a tree for instance given this tree we want to sum up the values of all the bottom nodes that would be these nodes in red for a total of nine now if you're really keen you can pause the video and give this problem a try to solve this problem all we need to do is perform a tree traversal and sum up the values of the leaf nodes as we encounter them during the traversal two popular traversal algorithms are doing a breadth-first search and a depth-first search now on trees the preferred traversal method is typically a depth-first search because it lends itself to be easily implemented recursively so that's what we're going to do it's pretty simple watch how the algorithm does it what you do is you start at the root and then you plunge down the tree depth-first at the end we sum up all the values and we can see that the sum of the leaf nodes is 9 now let's look at some pseudocode for how this is implemented the algorithm is quite short but it may look strange at first if you haven't seen much recursive code we call the leaf sum function by passing in a reference to the root node as a starting point inside the leaf sum function the first thing we do is handle the special case where we're given an empty tree and if this is the situation then we return 0 next we check if the current node is a leaf node and if it is then we return the value stored in the leaf node the is leaf method checks if a node is a leaf node by counting all its children if the number of child nodes is 0 then we know that the current node is indeed a leaf node if the node is not a leaf node then we iterate over all its children and call the leaf some method recursively summing over the return values this ensures that we traverse the entire tree and properly accumulate values finally once we are finished computing the sum for this node and its subtree returned the total and that's all for summing up the leaf node values in a tree our second problem today is a classic problem in computer science which is to find the height of a binary tree the height of a tree is defined as the number of edges from the root node to the lowest leaf of the tree here the leftmost tree has a height of 0 because it has no edges the middle tree has height of 1 and the rightmost tree has a height of 3 because the longest path from the root to the lowest leaf is 3 to solve this problem we're going to break it down and define a new function called H of X which returns the height of the subtree rooted at node X this new function allows us to start thinking not only about the height of a tree as whole but also the height of the sub-trees within our tree which are going to help us find the overall height for example on this slide h of a has a value of 3 but h of b has a value of 2 and h of e has a value of 0 by themselves leaf nodes such as node E don't have children so they don't add any additional height to the tree so we conclude that as a base case the height of any leaf node should be 0 now assuming Note X is not a leaf node we're able to formulate a recurrence relation for the height which is that the height of a subtree rooted at node X is the maximum of the height of X's left and right subtrees plus 1 let's have a closer look at how this works with an example suppose we have a tree and we want to compute its height so we start at the root and then we recursively Traverse down the tree depth first when we encounter a leaf node we give it a height of 0 and return we can't compute the height of a node until we know the height of all children so we visit the right node the right node is also a leaf node so it gets a height of 0 on the callback we have visited both children of the current node so we take the maximum heights of the left and the right children and add one for a total of 1 we just finished exploring the right half the tree now let's finish the left side it doesn't matter which side you do first as long as you explore the whole tree while you do your depth-first search we have found another leaf node so it gets a height of 0 we found another leaf node and another leaf node on the kullback-- take the max and add 1 take the max and add one again finally compute the height of the final node by taking the max and adding one and there you have it how to find the height of a tree let's have a look at some pseudocode shall we this is the tree height function it is responsible for computing the height of the tree you would start by calling this function by passing in the trees root node as we did for the leaf sum function the first thing we do is handle the empty tree case the height of an empty tree is undefined so return minus one next we check whether the current node is a leaf node by checking if both its left and right child nodes are null and return zero if either of them are not null then we know that this node has more children and we need to keep digging further down the tree in the event we haven't found the leaf node return the maximum height of the left subtree and the right subtree plus one I want to take a moment and go back to the previous statement and remark on a simplification we can exploit what do you reckon happens if we remove checking whether a node is a leaf node or not do you think the algorithm will still behave correctly pause the video and think this over oddly enough removing the leaf node check still makes the algorithm work correctly this works because the base case has adopted a new meaning instead of the base case checking for leaf nodes it's now checking whether a node is null and returning minus one now returning minus one is not only for handling the empty tree case but also to help in correcting for the right tree height let's see what I mean by correcting for the right height if our new base case is now checking for null nodes instead of leaf nodes then our tree is one unit taller so we need to correct for that for the sake of being thorough let's see how the height is calculated with this new base case once we reach a null node to return -1 on the recursive call back remember that we always add +1 with our recurrence so when we add up the counts you see that we get the correct height of 3 and that's how you compute the height of a tree in practice if you're designing a data structure where the tree height is important you can dynamically keep track of the height as you create the tree and insert nodes instead of fully completing the height every time like we're doing here but of course that isn't always doable alright folks thanks for watching please like and subscribe if you learned something and I will catch you [Music]