You’ll need to be able to work with groups or collections of items. A game that only has one character with one quest and with one shop that sells one item isn’t going to be very fun. You have choices and this episode continues more than a week long exploration of collection types available. You’ll learn when to use each type of collection and why. Up today is the binary tree. I’ll explain what binary trees are and then give you some guidance on when to use them.

If we add the numbers 3, 5, 1, 2, and 4 to a binary tree, it’ll look something like this. I have to break up left and right child pointer on their own line and some of the lines repeat.

root -> node(3)

node(3).left <-> node(1)

node(3).right <-> node(5)

node(1).right <-> node(2)

node(5).left <-> node(4)

What this shows is the the root of the tree is node(3) and node(3) does not point to any parent. node(3) has two children and the left and right pointers each point to a child. Each child also points back to node(3).

It also shows that node(1) has a child of its own on the right which is node(2) and that node(2) points back to node(1) for a parent. And then node(5) has a child on its left which is node(4) and node(4) points back to node(5) for its parent.

The height of a tree that is completely full is equal to the log base 2 of the number of items in the tree. We want to keep our trees as full as possible because if there are too many paths that extend farther than others, then searches down these long paths take longer than Big-O (lg N)