Please don’t teach trees as undirected graphs
I think I’m not alone in suggesting that the tree, and perhaps the binary tree specifically, is the most foundational data structure in computer science.
This raises the question of how binary trees should be introduced, and I’d like to make the case that introducing binary trees as a special case of undirected graphs is not a good idea.
I can see reasons why you might think this is a good idea; they both involve connecting circles with straight lines on the board. If you take the general notion of a graph, and you happen to arrange the lines and circles in a particular way, it’s a tree. That kind of suggests that graphs are a generalization of trees, and that you might want to introduce trees as a special case of these graphs.
Please do not do this.
Specifically, my claim is that this produces a complex definition of trees with many global constraints, a definition which makes it very hard to prove some simple things.
Let’s see why.
Trees as Undirected Graphs
To begin with, consider the definition of a graph, a set of nodes along with a symmetric binary relation on nodes that we call “edges”.
In order to construct the set of trees, we can restrict this definition in the following ways.
A tree is a graph with the following properties:
- We designate one node as the root node,
- it is connected, and
- it has no cycles.
The last two of these are global cqnstraints requiring complex checks, and verifying the third is genuinely quite complex, especially for a first-year student.
Suppose now that we want to identify the descendants of a node. This is where things start to get really unpleasant. The descendants of a node are the adjacent nodes that are not the parent node. But which is the parent node? The root node has no parent node. For other nodes, it is the adjacent node which is the first along the path to the root node. Again, this is not a simple process; if we provide a symmetric edge relation and a parent node, determining the path to the root node (and thus the parent node (and thus, by elimination, the descendants)) requires potentially a full search of the tree. Yes, this can be cached. Yes, it doesn’t matter whether you do a depth-first or breadth-first search. It’s still a lot of work.
But wait! Suppose we want a binary tree? Firstly, we must ensure that every node has at most two descendants, which is the same as ensuring that the root node has at most 2, and every other node has at most 3. That’s the easy part, though. In a binary tree we typically care whether a child is the left child or the right child; adding this to a graph representation requires labeling every node as either a left child or a right child, and then checking to make sure that no node has more than one left or right child.
Inductively Specified Trees
Okay, so what’s the alternative?
The alternative is the inductive specification of a binary tree: a binary tree is either an empty tree, or it is a node containing a left tree and a right tree.
This representation is essentially a tree by definition; no global checks are required. Asking whether a binary tree specified in this way is a binary tree is genuinely trivial: only binary trees can be specified using this schema.
You could argue that inductive specifications are hard for students, and I wouldn’t completely disagree, but I would also argue that the overwhelming simplicity of this definition of binary trees powerfully outweighs the challenge of becoming comfortable with inductive specifications.
Identifying the descendants of a node here is essentially trivial; an empty tree has no descendants, a non-empty tree lists its two descendants.
Freebie: this representation also sidesteps the irritating issues around identity which bedevil programmers everywhere.
What about directed graphs?
Trees as Directed Graphs
Directed graphs are considerably better than undirected graphs. But still way worse than the inductive specification. Specifically, you need an undirected graph that is connected and with no directed cycles, and you also need an additional constraint that at most one node points to another one (making the arbitrary choice that the edges point from parents to children). Checking these constraints still requires examining the whole graph. Identifying the child nodes is much nicer. Distinguishing the left and right children is still a serious problem.
Done
To summarize; it’s reasonable to talk about the correspondence between these two representations. You might even want to try to prove them isomorphic. But please don’t introduce trees as a special case of graphs.