Graphs: Trees
Graphs: Trees
What's a tree, if you stop to really think about it? Is it
- a root?
- branches?
- some leaves?
- a metaphor for parenthood?
One thing's for sure: get enough of them together, and you've got a forest.
Graph theory also has its own version of a tree—and it uses most of the same terminology, too.
![A graph theory tree.](https://media1.shmoop.com/shmooc/ap-computer-science/Graphs_images_pt1/Graphs4.png)
This is a tree. No, we aren't trying to gaslight you. This is actually a tree. At least according to graph theorists.
This kind of tree is an undirected graph with only one possible path between any two vertices or nodes. Translation: there can't be any cycles. In our humble opinion, that takes a lot of the intrigue out of the possible ways to get around the graph, but trees can still do some pretty amazing things.
Because there aren't any cycles, each node can have children, which are just the nodes that are connected below it. 7 and 9 are 8's children, and 6 is 7's child.
Plus, if you flip it over, it kind-of looks like a tree.
![That same tree, but flipped upside-down.](https://media1.shmoop.com/shmooc/ap-computer-science/Graphs_images_pt1/Graphs5.png)
See? See? Just imagine it as a little greener with a trunk below the upside-down 5.
Rooted Trees
A rooted tree is probably the reason trees were given the name, "tree." As long as you ignore the fact that they're upside down (defying gravity), they look just like trees. They also have
- a root, which is the node at the top that's directly connected to everything.
- leaves, which are the opposite of the root. They're where the tree ends—the nodes with no child nodes to speak of.
- branches, which are just the edges on the tree, except…uh…treeified.
A rooted tree has one—count 'em—one root. This root is usually at the top and has a direct path down to every other node. If your path from one node to another has to go up before it goes down, it isn't a root.
Take a look at this tree again:
![The same graph theory tree from before. The root is labeled with a 5. Its children are 3 and 8; their children are 4 (belonging to 3), 7, and 9 (belonging to 8). 7's child is 6.](https://media1.shmoop.com/shmooc/ap-computer-science/Graphs_images_pt1/Graphs4.png)
Going from the 5 to any other number means heading straight down the tree. If you take 7, you can go straight down to get to 6, but reaching any other node is going to mean going up and then down.
You can also look at the tree in terms of how many branches you have to take to get from the root to the node you need. The longest path from the root to the farthest leaf is called a tree's depth. The root sits at the 0th level (computer scientists’ favorite number after their ironically picked first-favorite number, 2) of that depth.
Nodes other than the root or leaves are called interior nodes and can be stacked into levels going outward from 0 (the root) to the leaves at level n.
Rooted trees can be directed, restricting how you move through them. If a rooted tree is directed, then you can only travel outward from the root, along the branches and toward the leaves. Or if terminology's more your thing: the root always has an in-degree of 0 and the leaves always have out-degrees of 0.
![A directed tree with a root of 4, child nodes 2 and 7, and grandchild nodes 1, 3, 5, and 9.](https://media1.shmoop.com/shmooc/ap-computer-science/Graphs_images_pt1/Graphs7.png)
Notice something weird?
Sometimes there's no possible path from one vertex to another, like from 3 to 4 or from 9 to 2. If a path does exist, there's only one, because we’re still talking about trees.
Trees might be a subcategory of graphs, but they're actually really important to graph theory, computer science, and life in general.
Seeing the Forest for the Trees
If you have a bunch of trees—rooted or not—all together but unconnected, is called a forest. It might look something like this:
![Three trees, including the original example, hanging out in the same picture.](https://media1.shmoop.com/shmooc/ap-computer-science/Graphs_images_pt1/Graphs8.png)
Yup, we really love the metaphors in computer science.