Week #8: Binary Trees

During week #7 we were introduced to Binary Trees.  A Binary Tree differs from the generic Tree design, as it contains nodes that have a maximum of two children referred to as left and right.

Here is an example of a Binary Tree:

When traversing a Binary Tree, there are three different orders in which the nodes can be visited:

1. Inorder: left child, root, right child

2. Preorder: root, left child, right child

3. Postorder: left child, right child, node

We can extend our understanding of a Binary Tree and create a Binary Search Tree (BST). A Binary Search Tree is ordered/sorted.  The left subtree always contains data less than the node data and the right subtree always contains data that are greater than the node data, therefore the data of the all node must be comparable.

Here is an example of a Binary Search Tree:

Efficiency of a Binary Search Tree

As mentioned in our class notes, if the tree of n nodes is "balanced", it will have a height of about log(n). Therefore when using this binary search tree to find data you will access about log(n) nodes. The structure of the BST depends entirely on the order of insertion of the items. Worst case scenario would be if you had to access n nodes (linear relationship) which is the same as having a list and going through every single item to find your desired data. A balanced BST is obviously more efficient.

Here is an example of a balanced BST vs and unbalanced BST: