CSC148 Binary Trees Post #6

After learning about Trees, we have moved into learning about Binary Trees. Really the only difference is that Binary Trees only have at most two children branching off the parent node. I found that for this topic, it was easier to understand than regular Trees because there were less children involved. I also found that the recursive code for Binary Trees to be a bit easier as well.

In class, we got two worksheets on Binary Trees. The first one talked about taking a look at the Binary Tree and evaluating the content of the Tree by first checking if the left and right nodes are empty and then recursively evaluating the left and right nodes.

The idea is that since we have only two children nodes, it is easy to represent a python expression with it, for example, the parent node could be an operator like "+" or "*", and the children nodes could be values such as 3.0 and 4.0. The recursive function would check if the children nodes are leafs, if not they will evaluate them using the parent node as the operator.

The second worksheet that we got goes into a bit more depth of what we can do with Binary Trees. Lets say that we have a Binary Tree with a ton of children nodes branching off and the root node contains some value. The problem is that we want to find a value that is somewhere in the Tree, but it would be inefficient to check every single node within the Tree.

How could we avoid that? Well Binary Trees have a special property where the values in the left side of the Tree will always be less than the value of the root node, and the right side of the Tree will be greater than the root node. If our root node value is 50, and the value we are looking for is 18, then we can immediately disregard the right side of the Tree and only look at the left side since everything on the right side will be greater than 50. This way we can save a lot of time and effort of having to check every single node in the Tree.

What is so great about this property is that when you implement it into a recursive function, we can continue to disregard the sides of the children nodes to even eliminate more checking required. From the previous example, lets say the value of the next child node from 50 on the left is 30. Since 18 is less than 30, we can disregard everything that is on the right side of 30 and focus on the left side, and we can do this again and again until we reach 18.

So Binary Trees are very friendly when it comes to searching for stuff in them, but I have yet to see a more practical use for them. Though compared to regular Trees, I think the difference is just in running time and which is more efficient. I also think that Binary Trees are rather job specific as well and that they are mainly used for their binary search properties. That is all for this week about Binary Trees, thanks for reading!