Many people told me they liked the cartoons from the first installment of Get Swifty, so I thought I’d apply the same concept to Data Structures and Algorithms.
Note: If you need a refresher on data structure trees and how they work, check out my article on trees here.
Sororitree rush season has started, and you’ve decided that you’re going to be a part of it. But what kind of structure would you like to join? Follow along as we visit each tree and learn their particular customs, initiation rituals, and why they insist on calling their littles their children.
By the end, you’ll have a good idea of which sororitree is the one for you.
Common Structures of Binary Trees
A binary tree is a tree where each node has two children max. It turns out that binary trees can assume many different shapes! The most common ones are shown above:
Perfect binary trees are exactly what they sound like. Each non-leaf node has exactly two children, and the structure is perfectly balanced — the leaf nodes all have the same depth.
Complete binary trees are like B-list perfect binary trees. Every layer except the last must be fully filled out. In the last layer, new nodes must start from the left side and continue to fill out.
Full binary trees don’t have any rule about being balanced or sticking to the left, but it does mandate that each non-leaf node must have exactly two children, no more and no less. (Sounds kind of apocalyptic, doesn’t it?)
Degenerate binary trees are binary trees where each parent node only has one child, and can lead to that weird arm-looking linked-list-esque shape that you see in the picture above. They remind me of the time I got away with wearing an extra-long sweater with leggings to my somewhat conservative private school — the sweater was technically also a dress, so it would be perfectly within dress code to have on my outfit. #trollTheAdministration2k13
You should now be able to look at a binary tree picture and recognize what kind it is based off of its shape. Later in this series, we’ll see specific binary tree implementations that could take on these shapes. See you next time!
Full v.s. Complete Binary Trees
Difference between “Complete binary tree”, “strict binary tree”,“full binary Tree”?, Stack Overflow
Wikipedia article on binary trees
Help Spread the Love!
If you have a friend who is trying to learn about Data Structures and Algorithms, and you think that this article could help them, please send it their way!