More With Trees
1. Introduction
In this set of notes we’ll expand a on binary trees by giving some additional terminology for them and discussing an alternative way to store them. We’ll need both of these as we move forward into other data structures that can be built from trees.
2. More Tree Vocabulary
Let’s look at three more vocabulary words related to binary trees.
2.1. Full Binary Tree
A full binary tree is a tree where each node has exactly 0 or 2 children.
2.2. Complete Binary Tree
A complete binary tree is one where every level except the last one is completely filled, and the last level has all leaves as far left as possible.
The following tree is not a complete binary tree because the level containing 7 and 12 is not full.
2.3. Perfect Binary Tree
A perfect binary tree is like a complete binary tree where the last level is also full. Another way to define it is to say that all internal nodes have two children and all leaf nodes are at the same depth.
All perfect trees are also full and complete.
3. Another Way to Store Trees
Consider the following binary tree:
Thus far, we’ve stored binary trees by creating TreeNodes who each have a left and right pointer and forming the tree that way. However, there is an alternative way to store a binary tree using an array. Here is an array representation of that same tree:
Notice the following properties:
The root is stored at position 0.
There is a spot in the array for every possible node in a perfect version of the tree.
For example, notice the empty space at location \(5\) for the missing left child of 26.
Also notice all the empty space starting at location \(9\); this is for the missing children at the bottom of the tree.
If a node is at location \(L\) in the tree, then its left child is at location \(2*L+1\) and its right child is at location \(2*L + 2\).
- For example, the node with value 7 is at location \(3\) in the tree. Its left child is at location \(7\) (\(2*3+1\)) and its right child is at location \(8\) (\(2*3 + 2\)).
If a node is at location \(L\) in the tree, then its parent is at location \(\frac{L-1}{2}\). (Integer division.)
- For example, considers the nodes with values 3 and 8, who both have 7 as their parent. Node 3 is at location \(7\), and \((7-1)/2=3\) so the parent is at \(3\). (Which is true.) Node 8 is at location \(8\), and \((8-1)/2=3\), so the parent is at \(3\). (Which is also true.)
This is a valid way to store trees, and is actually simpler than storing pointers to nodes and such. The main downside of this approach, however, is wasted space. If a tree isn’t perfect, then there are empty spaces in the array.