Tree’s & Binary Search tree’s

I recently learned a little bit about tree’s and binary search trees and thought it could be a cool topic to talk about for my first blog as a student at Flatiron School. In the blog I am going to try and put to words what I learned about. Tree’s and binary search tree’s seem super cool and interesting to me and I think they play a very important role in learning and understanding algorithms.

First thing I learned is that tree’s have nodes and links/edges. One of the most crucial part of a tree is the root node and technically it is all you need to make a tree. A root node can connect to other nodes which are called child nodes. The connection between a root node and its children is called a link/edge. A parent node is any node that has descendants from it, and sibling nodes share a common ancestral parent. A leaf node is a node without any children and the last on the chain. Any node that is not a leaf node is called an internal node or any node that is a child and isn’t a leaf will be an internal node.

One important thing I learned is that tree structures are not linear, and nodes can connect to nodes in different ways but the data always has the hierarchy. The fundamental truth to trees is with the relationship of nodes as compared to the ratio of edges. A single tree can only have one single root node. There is a rule for trees that if you have n number of nodes you will always have n-1 links/edges. We can prove this by only having one root node by nothing can ever be linking to it. A root node can have children of its own but it will never have a parent. Another interesting fact is that tree’s are recursive structures. All this means is that one tree structure can contain mini trees within it. The technical term for this is called a subtree. Tree’s can contain nested subtree’s within them which is actually what makes them recursive structures. The recursive aspect of trees becomes important when we want to run algorithms on a tree data structure.

One important thing to know is what kind of tree we are working with. There are two important properties that help us classify and understand trees even further. These two properties are the height and depth of a tree and the nodes within it. To find the depth you would ask yourself how far away is the node from the root node that we are trying to track. Height is sort of the same but you must count the links/edges from the node you are trying to track to the furthest leaf node. In other words what is the branch height of this node we are looking at. You can think of the structure of a tree just like a tree in nature but flipped upside down. The height of the root node will always be one more than its child. The height of the root node is also the height of the entire tree.

One reason it is important to understand the height and depth of the tree is it gives us insight as to what the tree looks like. Because there are balanced trees and unbalanced trees knowing the height and depth helps us to determine what we are working with and how to work with it. A balanced tree is a tree where any two siblings do not differ in height by more than one level. If there are two subtrees that are siblings that differ in height for more than one level they are unbalanced trees. Knowing what we are dealing with will help us down the road when we try to decide what to do with the tree.

Another thing that I learned a little bit about was binary search trees which are made up of basically a left subtree and a right subtree. Binary search trees much be sorted into a specific order and follow specific rules so that the nodes appear in a specific order. The general rule for sorting a binary search tree is everything in the left subtree of the root node has to be smaller in value of whatever the root node is. And everything in the right subtree must be greater in value than the root node itself. Also within the subtree the element that is to the right of the subtrees root must also be bigger in value. The left subtree must also follow similar rules that the left subtree root must have a lesser value on the left element of its parent node. These rules are important to know so we can see where we can insert new nodes. This is the heart of binary search.

Binary search trees leverage the power of the binary search algorithm. The Binary search algorithm is one of the most effective and well known ways of searching for an element is computer science. Formally a binary search algorithm is an algorithm that divides and conquers data, making it easy to find an element in a large data set. Binary search simplifies and speeds up the process of searching by dividing one data into half every time it takes a step. Binary search does not work well if the tree we are working with is unbalanced. One git hub command is git bisect that uses binary search in a way to search through a bunch of commits by asking you if they are good or bad and then narrows down the bad commit. Something like this seems super cool to me and maybe one day I will be a pro at binary search algorithms.

I have only just cracked the ice with my learning about tree’s and binary search tree’s. I know there is tons and tons of information and things to be learned about tree’s, binary search tree’s and algorithms, so I plan on learning as much as I can about them in my career as a software engineer. This topic was very fun for me to write about and I hope you enjoyed!