41: Collections: Binary Tree.

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) Listen to the full episode or read the full transcript below. Transcript There are a lot of different kinds of trees and we’ll have future episodes that explore in detail various types of trees. I’ll explain today binary trees. All the tree collection types get their name because the structure resembles an upside down tree. A tree starts out with a main trunk that splits into various branches. The number of branches gets larger as the branches themselves get smaller. And at the end of the branches are leaves. Now imagine turning this upside down and replacing the trunk with a single instance of one of your classes. This is called the root. I know, that never made sense to me either. Why would there only be one root and why would it be sticking up in the air? For that matter, why is the tree upside down in the first place? All I can say is you’ll get used to it. The root is a node just like you have nodes in a list. And like a list, this node class is designed specifically for the type of tree it belongs to. Binary trees have nodes that contain three pointers. Instead of binary tree nodes pointing to previous and next nodes like you’ll find in a double linked list, a binary tree node is arranged in a hierarchy. It has a parent pointer and two children pointers. The children pointers are called the left child and the right child. There are two very special properties that makes a tree a binary tree. Binary means two. That’s why there’re two child nodes. If you have three, or four, or some other number of child nodes, then you don’t have a binary tree. The other special property is how the left and right child nodes relate to their parent. The primary requirement of being able to use a binary tree is that you must be able to compare your items to see if one item is less than, or equal to, or greater than another item. If you can’t compare your items, then a binary tree just won’t work to hold those items. If you’ve ever been in a group photo, then you know that putting shorter people behind taller people doesn’t work very well. If you’ve got enough room for two rows, then you really want to make sure that those in front are either shorter or sitting. Binary trees get their structure by arranging new items in the left child position or the right child position based on how the new items compare with the existing