If you've ever really looked at broccoli—even if it's been with pure hatred—you might have noticed that it matches the theme of the learning guide. No, we aren't saying that it looks like a tree (though if you're thinking of making an edible diagram of A Tree Grows in Brooklyn, you might want to hit up that part of the vegetable aisle), but it also grows kind-of like a computer science tree.

Take a good, long look at Romanesco broccoli and you'll see it growing in identical spirals that get smaller and smaller. You can call something that forms an identical, smaller copy of itself a fractal, which is exactly what broccoli and trees are.

Fractals look the same no matter how much you zoom in or out of them. Do it again and you'll have two more identical copies. Keep doing it and you'll have…a pile of broccoli dust, but before that you'll have a bunch of tiny pieces of broccoli that all look the same. That's how fractals work. Both Romanesco broccoli and normal, non-Italian broccoli are examples of n-ary trees.

n-ary trees are just like binary trees, except they have the ability to branch out to n nodes per node. They're considered fractals because no matter which internal node you choose, the nodes connected downward and outward from it make another, smaller tree.

 

If the tree's full, all nodes in the tree (with the exception of the leaves) have an out-degree equal to n, just like this guy, where n equals 2:

 

Even full trees don’t completely follow fractaling rules because they might have some empty spaces left to fill at the bottommost layer. The perfectionist's dream in trees—at least in computer science—is when all nodes (besides the leaves, of course) in the tree have an out-degree equal to n. That's what it's called, BTW: perfect.

This ternary tree is perfect (and can win any upcoming CS pageant contests). It’s also full, but you can’t have a perfect tree without it also being full.

 

In theory, you can make any n-ary tree with any number filling in for n. Just pick your favorite number and run with it. In the real world (if by "real world" you mean digital world), though, n-ary trees get ridiculously complicated once n goes above 4 or 5. On the other end, unary trees (n equals 1) are would-rather-jab-a-fork-in-your-eye boring. They're also usually called linked lists.

Oh hey. We have a learning guide on that too. Isn't that convenient?

(Source)

Binary Trees

Since computer scientists call themselves groupies of the number 2, binary trees are their favorite n-ary trees. Of course, binary trees are also really easy to program when you're working on a binary-based digital computer.

Coincidence? We think not.

What’s not-so-easy is trying to describe trees without using metaphors, which brings us to the mixed metaphor where computer scientists forgot they were using actual trees and decided to start comparing trees to family trees.

Unlike some family trees (but like others), all child nodes only have one parent, which is just the node above them. The parent of all the nodes is the root. Like the protagonist in most Dickens novels, the root itself is an orphan and has no parents.

Binary trees, just like any other n-ary tree, can be perfect and full or just full. When a binary tree is complete, each level except for the last is full and all its nodes are filled up from left to right (instead of just going anywhere).

This binary tree is full:

 

This one is complete:

 

This one is both.

 

If a binary tree is neither complete nor full, it can look a little unbalanced.

 

Computer scientists like things to look orderly, meaning that they want to make binary trees as balanced and complete as possible. That way, when they search for something, they don't have to spend an unnecessary amount of time heading down the tree.

Trees like that last one are a computer scientist’s worst nightmare. They’re messy and inefficient to search. But if you're a big fan of chaos and slow runtimes, we won't stop you.

Unless you're trying to sell us software full of these kinds of trees. Then we will stop you.