Binary Trees

Before the reading week we started to work on binary trees. A binary tree consists of several nodes. One of these nodes is the root which is the one on the centre. Root has two children, a left and a right one. The children can also be another binary tree or they can be empty. If a binary tree has no children then it is considered a leaf. If it has any children it is a internal node.

A binary tree can be shown like this:

Since binary trees are stored inside of each other, most applications done on them are easily done using recursion. An example would be traversals. A traversal of a binary tree is a way of writing the tree as a unnested list. As we did in class there are a few different tree traversals. Let's focus on in-order traversal, because I like that one the most since it seems as it is the most natural one.

To make an in-order traversal of a binary tree what you have to do is take the in-order traversal of the  left child of root add the root than add the in-order traversal of the right child of root. It can be clearly understood that this is a recursive function. My way of telling how to do an in-order traversal includes doing in-order traversals in it so there you go. So, the in-order traversal of the tree pictured above would be [2, 7, 5, 6, 11, 2, 5, 4, 9]. It's kind of late, so correct me if this list is wrong, but you'll get the idea.

Trees can be written as nested lists or we can declare them as a class. Traversals are only one thing we can recursively implement on trees, I'm sure we will work on them trying to do more complicated stuff in the coming lectures and labs. Take care!