Trees study guide

A reliable reasoning method

When given a diagram or description, separate the questions that are often combined. First ask whether the structure is a tree. Check that it is connected: there must be a route between every pair of vertices. Check also that it has no cycles: no route should loop back to a vertex and form a closed path. If either condition fails, it is not a tree under the stated definition.

Next ask whether a root has been designated. If no vertex is special, describe the structure simply as a tree. If one vertex is designated, it is a rooted tree. The root is the only node with no parent, and every other node is a descendant of the root. The selected root determines the parent–child relationships used when explaining the structure.

Finally, check the child limit. A rooted tree is a binary tree only when each node has at most two children. A node with zero children does not violate the rule, and a node with one child does not violate it either. A node with three children does violate it, so the structure is not binary under that rooting.

Worked application

Consider a connected, undirected structure with no cycle. Before a root is selected, the safest description is “tree”. If a particular vertex is selected as the root, describe it as a rooted tree and identify the root’s children. Continue from each child to identify further descendants and their parents. If the description shows that no node has more than two children, conclude that it is a binary tree as well. This reasoning works in layers: tree properties first, rooting second, and the binary restriction third.

Changing the designated root changes which node is described as the parent of another node. It does not change the fact that the underlying structure has the same vertices and edges. Consequently, a response should state the chosen root before listing parent–child relationships. Do not infer a root merely because a diagram is drawn with one node at the top; the root must be designated or clearly indicated by the context.

Exam application

For a definition question, include all essential parts rather than only saying that a tree is hierarchical: a tree is a connected, undirected graph with no cycles. For a comparison question, state that a tree need not have a root, whereas a rooted tree has one designated vertex and therefore parent–child relationships. For a binary-tree question, state that it is a rooted tree and that each node has at most two children.

For a structure-classification question, explain your decision rather than naming the category only. For example: “It is a tree because it is connected and has no cycles. It is rooted because one vertex is designated as the root. It is binary because no node has more than two children.” If a condition is not met, identify the exact failed condition, such as disconnection, a cycle, no designated root when a rooted tree is required, or a node with more than two children when a binary tree is required.

Self-check

1. Can you define a tree without referring to a root?
2. Can you explain why a rooted tree has exactly one node with no parent?
3. Can you distinguish a descendant from the root itself?
4. Can you explain why “at most two” permits zero or one child?
5. Given a diagram, can you check connectedness, cycles, the designated root, and the child limit in that order?
6. Can you state that a binary search tree is a common application of a binary tree without replacing the binary-tree definition with an application-specific description?

A strong answer uses the structure’s properties as evidence and keeps the terms tree, rooted tree, and binary tree distinct.