Trees revision notes

What is a tree?

A tree is a connected, undirected graph with no cycles. Connected means that every vertex can be reached from every other vertex by following edges. Undirected means that an edge has no direction. A cycle is a path that returns to its starting vertex without repeating the relevant vertices along the way. Therefore, a graph is not a tree if it is disconnected or if it contains a cycle.

A tree does not have to have a root. The vertices and edges alone can form a tree without any vertex being treated as special.

Rooted trees

A rooted tree is a tree in which one vertex has been designated as the root. Designating a root gives the nodes parent–child relationships. The root is the only node with no parent. Every other node is a descendant of the root.

The same underlying tree can produce different rooted-tree relationships if a different vertex is selected as the root. The edges do not become directed graph edges; rather, the root gives a way to describe which node is the parent and which node is the child.

Rooted trees are useful when information has a hierarchical relationship. The hierarchy can be described by starting at the root and moving through parent–child relationships. When interpreting a rooted tree, first identify the root, then determine the parent of each other node and the descendants reached below it.

Binary trees

A binary tree is a rooted tree in which each node has at most two children. “At most two” means that a node may have zero, one or two children; it does not mean that every node must have exactly two. A binary tree is therefore also a rooted tree, so it has a designated root and parent–child relationships.

A common application of a binary tree is a binary search tree. The important classification here is that a binary search tree is an application of a binary tree; the defining tree restriction is that each node has no more than two children.

Worked classification

Suppose a graph is connected and has no cycles. It satisfies the definition of a tree, even if no vertex has been selected as a root. If one vertex is then designated as the root, it becomes a rooted tree, with the root as the only node without a parent. If every node has at most two children under that rooting, it is also a binary tree.

Common errors

• Calling every tree a rooted tree: a tree may have no designated root.
• Treating a root as an extra node: the root is one of the existing vertices.
• Saying that a binary tree must give every node two children: the condition is at most two.
• Forgetting that a rooted tree is still a tree: it must remain connected and have no cycles.
• Confusing parent–child relationships with the original undirected edges: the relationships are determined by the chosen root.