Binary Tree Challenges

     

    For this week I decided to step into more complicated challenges that take use of a binary tree. A binary tree is one of the most common algorithms that is used in coding interviews so its important to understand the ins and outs of it. The first image above is a visual image of what the algorithm actually looks like. Think of every circle as a node or an object that is attached to our algorithm. The very first node on the top is called the root node. Every node after that are children nodes and children nodes can also have children nodes as well. When a node is not pointing to anything like the 4, 7, 13 they are called lead nodes. In this case we can take a guess that the values that were put in were in order [8,3,10,14,13,1,6,4,7]. This might be incorrect but its just a guess to explain what is happening in this image. The first value added would be the 8 and it becomes the root node because its the very first node in our tree. Then we add three. If three is less than 8 then we add it to the left of the tree. Then we add 10. Since 10 is greater than 8 we add it to the right. The comes 10, since 10 is greater than 8 we add it to the right. Once we get to 14 we check if its greater than 8. It is so we go to the right node. We check if its greater or less than 10 which it is so it goes to the right of 10. This happens to every value/node that is being added to the tree. Every node has a left pointer, a right pointer and a value. Once we get to the root nodes we set it that they are pointing left and right to null which means empty or none. 

    The first problem we have is called find the closest value in a binary search tree. This is the problem. You are given a binary tree and a target integer. Our goal is to try to find the closest value to the target integer that exists in our binary tree and return it to the user. Visually it is very easy for us to look at a binary tree and tell which value is the closest but a compute does not have an eagles view of a binary tree like we do so we have to traverse every node one by one. This is how I solved this problem.

    I am currently taking csc240 and we have been practicing recursion this first quarter of the semester. Recursion is when a method calls on it self to run again. This was the perfect way to solve this problem. Since we are only given a tree and the target as parameters in the problem I decided to create a helper method called findClosestValueHelper that way I can pass a third parameter called closest_value so I can keep updating it and calling it recursively through my solution. When I call the helper method in my original method I pass the value as infinity set equal to closest_value to start. This can also be set to the the roots value it doesn't really matter it all depends on the programmer. Once we are inside of our helper method I create a new variable called current_node = tree so that we can visually see better that we are currently on the current node. Since we are using recursion we have to set a base case to stop the recursion or else our method will be called infinitely. So when would we stop calling the method again? Well we would stop when the node we are at has no value. In my explanation of binary trees I mentioned that once we are at the end of our trees known as "leafs" the next step down would be pointing to null. So when we reach the null or none we know we have gone past our trees scope. So if the tree or current_node is none/empty then we just return the value of the closest_value.

    Next in our solution if our node is not empty we have to check if the value of the current node is closer to our target than the current value in it. Let's just say for example our target given is 13. Remember that closest_value is initially set to infinity. The way we calculate this is by taking the the absolute value of closest_value - target and current_node_value-target and check if the first equation is greater than the second. We take the absolute value because we dont care if its negative or positive we are just concerned with the distance. Let's take the root node for example. In our first method call it would be abs(infinity-13) and abs(8-13). Well infinity - anything is just infinity and abs(8-13) is 5. A difference of 5 is closer to our target than infinity so we update the closest_value variable to 8(current_node_value). We then move on to the recursion part of our code. 

    Then next part of our code is to decide if we are going to move down the left part of our binary tree or the right part. Remember that the left part of the tree are values that are less than the current node and the right part of the tree are values that are greater than the current nodes value. Our first condition is to check if the target is less than our current node value. If it is then we will call the method again. However in our parameters when we pass our tree we will go down the left side of the tree calling tree.left. This is because if our target is less than the current nodes value, any value greater than that value would have a greater distance to our target so it would not be helpful going down the right side. If our target is greater than the current nodes value then we will recursively call the method but this time we will go down the right side. Our last case is if the current_node value is equal to the target. If that is true we will simply return the closest_value and stop going down the tree. That is because if the current_node value is equal to the target that is as close as we can get and we simply return that value to the user. 

    For our second problem it still deals with binary search tree except this one is called node depths. We are trying to find the total depth of all the nodes added together and returned to the user. For example in our first image the depth of node 8 is 0 since its the root node. The depth of node 3 is 1. The depth of node 1 is 2. The depth of node 6 is also 2. The depth of node 4 is 3 and so on. We then need to add all these values and return it to the user. Since there is not a way to go reverse in a tree we have to figure out a way of passing the current depth value down every time we go down the tree. This is why I love recursion. 

    Since the problem only gives us a parameter of a tree we have to call a helper method that way when we  can recursively update the total_distance of the nodes added all together recursively. First I create a variable called current_node = tree which tells us which node we are currently on. Now for recursion we always have to set a base case to avoid an infinite loop. Our base case will be when the current node is empty because we know that we have gone to a null node. At that point we would just return the value 0 and not call the method again. If not we return the total distance plus the recursion method of the node going to the left and another recursion method of the node going to the right. The only difference is in these recursive calls we are adding one to the value of the total distance in the parameter. That way as we go down the tree we know that the depth is plus 1 from the previous and in those calls we are adding that distance to our total as well.