Binary Tree — Part 1
What the heck is a binary tree? A tree made up of 1s and 0s?! No no no, but actually… maybe that’s not too far off. If you were to visualize this, a “binary root structure” would actually make more sense since we think of this from the parent most root and work down, but “tree” is a better word choice. The choice to use “binary” is actually perfect because there are only two options from each branch. Let’s start with some terms so we can use them and collect our thoughts:
- trees: a data structure that connects nodes in a parent-child relationship.
- root node: root node is the only node in a tree without a parent.
- node: Each parent node has a pointer to its children nodes, and therefore knows about its children (are they null? do they have a value and what is it?)
- sibling node: siblings are nodes who share a parent node
- branch: a connection from parent node to child node
- leaf node: the node at the end of a branch
- left node: the left node will always be less than the parent node
- right node: the right node will always be greater than the parent node
Ok, that’s great… a picture please!
Uh, that’s a pretty lame tree…
Well, yes, lame but very clear. Our node.leftNode (1) is less than it’s parentNode (2), and it’s respective sibling node, node.rightNode (3) is greater than their parentNode. Now this isn’t to say every tree is going to be like this, but this is the basic concept.
Let’s get a little more detailed about our binary tree. Similarly how all trees aren’t the same or even all walnut trees aren’t the same, there are different types of binary trees! Fortunately, this is diving a bit deeper, but it’s still fun to learn!
- rooted binary tree: the technical name for a binary tree since it’s definition is, “ a tree with a root node and every node has a most, two children.” So (for fun) every subset of a binary tree is a rooted binary tree, but all binary trees are not the same subset of binary trees.
- full binary tree: when each branch is full (2 nodes) or empty (0 nodes), the tree is full.
- complete binary tree: every level is completely filled with the exception of possibly the last, and all nodes in that last level are as far left as possible. Could look like a pyramid, or lopsided to the left.
- perfect binary tree: all leaf nodes are at the same level, and all internal nodes are full. Basically, it’s going to look like a pyramid.
- infinite complete binary tree: every node has two nodes. My understanding of this is that, like it’s name, it’s an infinitely growing binary tree. So, this is the invasive species of the lot…
- balanced binary tree: a leaf is not much further away from the root than any other leaf. (Yes, that leaves some room for interpretation depending on how much variance is permitted in balancing.) Another way to think about it: the left and right subtrees of every node aren’t different in height by more than 1 level.
- degenerate binary tree: every internal node has only one child. So, this is a vine, not really a tree…
