What’s a tree? Don’t try to give us some perennial plant photosynthesis mumbo jumbo from biology or botany or arboriculture or whatever. This is computer science, not those other sciences. They have their trees and we have ours.

Their trees have lots of roots that go down and branches that go up. Computer science trees are more like upside down trees without roots, or trees that just got cut down so all that’s left are stumps and roots.

You know what, this will be a lot easier if we just show you one of our trees.

They look a little something like this:

 

Bet you didn’t see that coming.

Computer science trees are actually special kinds of graphs that you can use to hold and search information. Trees are a special case, though, where you can only have one path or route from one node (those green, numbered circles) to any other node.

Just like your favorite climbing trees, computer science trees have

• a root
• leaves
• branches

and they even cluster together in forests. Instead of growing up from the roots, though, they start from one root and grow downward (in this case, that root's 12). The nodes connected to the root are called the root's children (7 and 15). Once you get to the bottom of the tree where nodes don't have any children of their own, you're looking at the leaves (3, 10, 13, and 18). Any time a node connects to another node, that connecting line is called a branch because…metaphors.

Oh, and the child/parent nodes that aren't quite roots or leaves are just called internal nodes. They (probably) originally wanted to name those nodes trunks, but people were getting too confused because

• trees usually only have one trunk.
• they didn't understand why you'd want to let a data structure go swimming.

Many trees are undirected—they let you go use any branch going any direction you want. That isn't always the case when it comes to graphs, but in this case you can go just as freely from 7 to 12 as you can from 12 to 7. It’s a two-way street.

Just like streets, trees can also be directed graphs—you can only go one direction on a branch. If your tree is directed, then all possible paths/edges around the tree will point outward from the root to the leaves. The only node that can reach every other node is the root.

 

Whether you've got a directed or an undirected tree, the height of that tree is always measured by how many levels of nodes the it has. (If computer scientists were really committed to the whole tree metaphor thing, they really should've called it the tree's rings.) Since computer scientists almost always start with zero, both trees here have a height of 2.

If your tree looks less like an idyllic oak tree and more like a windswept pine holding onto the side of a cliff for dear life, the same number of nodes could have a dramatically different height. As long as the tree has at least one node on a level, that level is counted in the height. That means these two trees actually have a height of 4.

 

Apart, they're just odd-looking, spindly trees. Together, they're…still odd-looking and spindly, but they're also known as a forest—a group of unconnected trees.

Any trees can be made into a forest as long as they aren't connected to each other. If they are actually connected, they're just one big tree, like aspens.