SFTPK: Binary Tree
This post is one in a series about stuff formally trained programmers know—the rest of the series can be found here. # Binary Tree
In the previous post, we looked at the tree pattern, which is a theoretical way of structuring data with many advantages. A tree is just a theory though, so what does an actual implementation of it look like?
A common data structure implementation is a binary tree. The name binary tree gives us a hint to how it is structured: each node can have at most 2 child nodes.
Classifications
As a binary tree has some flexibility in it, several classifications have emerged to discuss a binary tree consistently. Common classifications are:
- Full binary tree: Each node in a binary tree can have zero, one, or two child nodes. In a full binary tree, each node must have either zero or two child nodes.
- Perfect binary tree: This is a full binary tree with the additional condition that all leaf nodes (i.e., nodes with no children) are at the same level or depth.
- Complete binary tree: The complete binary tree is where each leaf node is as far left as possible.
- Balanced binary tree: A balanced binary tree is a tree where the height of the tree is as small as possible (ideally, logarithmic in relation to the number of nodes).
Implementations
While a binary tree is more than just a pattern, there are no out-of-the-box implementations in C#, Java, or JavaScript for it. The reason is that it is a very simple data structure—so if you need just the data structure, you could implement it yourself. More importantly, you likely want more than the simple structure—you want a structure that optimizes for traversal or data management.