I've often found binary trees as a data structure to be intimidating, and that will not stand! I refuse to let any binary defeat me! (Just some enby humor for you.) So I'll take my next few blog posts to break them down into very manageable bite sized pieces.
In this first installment, I'll cover just the basics of what a binary tree consists of, and what types are most common. We can get into coding them and traversing them down the line. Big props to Cracking the Coding Interview (CTCI) for being my source for basically all of this.
A tree is a data structure that starts with one root node, which has zero or more child nodes. Each child node also can have child nodes. The result is a spreading 'tree' of data. Trees don't have to be binary, they can have up to any number of nodes. Here is a ternary tree for instance, which has three child nodes off its initial root node.
The most common type of tree used though, especially in a programming interview, is a binary tree. A binary tree can have up to two children per node. Here's an example:
If it's just a plain ol' binary tree, the order of these nodes doesn't matter. Where things start getting interesting and useful is with a Binary Search Tree. Those are in a particular order so that you can search through them to find something. On page 101 of Cracking the Coding Interview, a binary search tree is defined as one where all nodes match this description: "all left descendants <= n < all right descendants." So basically, the nodes are ordered from left to right, bottom to top. Here is a sorted binary search tree: 
This sorting is what makes it useful for algorithms. You can traverse through these trees to determine various useful things about your data set, but we'll go over how to do that in another post. for now, let's go over a few more qualities of binary trees. Terms you may see are Complete, Full, and Perfect. These things are all similar but distinct.
A Complete binary tree is one where every level of the tree must be fully filled, except the bottom level. The bottom level fills left to right if it is not full. Here is an example of a complete binary tree: 
.
You can see that in this example the bottom level is not full, but both leaf nodes are on the far left. (A Leaf Node is one with no children.)
Slightly different is a Full binary tree. On a full tree, every node has either two or zero children. Here's an example: 
Finally there's Perfect trees, which are very uncommon. A perfect tree is both full and complete, meaning every node has two children, except those on the bottom most level, which are all leaf nodes with zero children. Here's the three side by side so you can get the idea: 
Perfect trees are very uncommon as we are just unlikely to get that lucky with our number of nodes.
Those are the basics of what forms a binary search tree! Next time, I'll get into the basics of executing one in code, as well as some of the complications that arise in implementing them - such as what to do with duplicate nodes.
Top comments (0)