Week 8 SLOG: Binary Trees and Binary Search Trees

In week 8, we learned about Binary Trees and Binary Search Trees.

Binary Trees are simply trees that have a node, and at max have two children under each node.

Binary Search Trees (BST) are a special type of binary tree. They have three distinguishing characteristics:
(1) All data in BSTs are comparable.
(2) The data in the left subtree are less than the root node
(3) The data in the right subtree are greater than the root node.

As such, they are useful when holding information that needs to be compared because the structure of a BST makes it very easy and efficient to traverse.

There are three different ways to traverse a Binary Tree: Preorder, Postorder, and Inorder.
The names of these traversals are very self-explanatory.
In Preorder, the main node is visited first, then the left subtree second, and finally the right subtree.
In Postorder, the left subtree is visited first, then the right subtree, and finally the node itself.
In Inorder, the left subtree is visited first, then the node itself, then finally the right subtree.