Trees

Overview

Recall questions on rooted and binary trees, parent, child and descendant, leaf nodes, and the ordering rule that governs a binary search tree.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Define a tree.

   Model answer

   A tree is a graph that is connected, undirected and free of cycles. Connected means there is a path between every pair of vertices; no cycles means there is no path that returns to its starting vertex without reusing an edge. Consequently there is exactly one path between any two vertices.

2. 2

   Does a tree have to have a root?

   Model answer

   No. A tree is simply a connected, undirected graph with no cycles, and that definition says nothing about a root. A root only exists when one vertex has been deliberately designated as such, which makes the tree a rooted tree. It is a common mistake to assume every tree has a root.

3. 3

   Define a rooted tree.

   Model answer

   Take any tree and single out one of its vertices as the root: what you have is a rooted tree. That one choice imposes parent-child relationships throughout the structure — the root alone has no parent, every other node descends from it, and each node's distance from the root fixes its level. The same underlying tree can yield several different rooted trees, depending on which vertex is chosen.

4. 4

   In a rooted tree, what is meant by parent, child and descendant?

   Model answer

   Once a root has been chosen, each node other than the root has exactly one parent, the node immediately above it on the unique path back to the root, and any nodes immediately below it are its children. A descendant of a node is any node that can be reached by moving downwards from it — its children, their children, and so on. Every node other than the root is a descendant of the root.

5. 5

   Define a binary tree.

   Model answer

   A binary tree is a rooted tree in which each node has at most two children. A node may therefore have two children, one child, or none at all, but never three or more.

6. 6

   What is a leaf node?

   Model answer

   A node in a rooted tree that has no children — nothing hangs below it. In a binary tree, a leaf is a node whose left and right child pointers are both null.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.