Chapter 6Graphs and Treesnotes.en.pdf:97-99

Trees

Rooted, branchy, no cycles

Def 6.3.4 — Tree (notes)Def 6.3.7 — Parent/child

Concept

A tree is a special kind of DAG that captures hierarchical structure. By
Definition 6.2.8 (notes p. 97), a tree is a DAG $G = \langle V, E \rangle$
satisfying:
1. There is exactly one initial node $v_r \in V$ (the root): $\text{indeg}(v_r) = 0$ .
2. Every other node has $\text{indeg}(v) = 1$ .

Equivalently (Lemma 6.2.10): for any node $v$ other than the root, there is
exactly one path from the root to $v$ .

Tree vocabulary (Definition 6.3.7):
- Parent of $w$ : vertex $v$ with $(v, w) \in E$ (so $w$ is a child of $v$ ).
- Root: the unique initial node (drawn at the top in CS).
- Leaf: a terminal node with no children.
- Ancestor / descendant: transitive closure of parent / child.
- Depth of a node: length of the unique path from the root to it.
- Height of a tree: maximum depth of any node (= length of the longest
root-to-leaf path).

Important fact (the "tree counting" lemma): an undirected tree with $n$
vertices has exactly $n - 1$ edges. This makes trees the minimum connected
graph on $n$ vertices — sparse and acyclic.

Tree examples in AI:
- Parse trees: terminals as leaves, grammatical categories as internal nodes.
- Decision trees: each internal node is a feature test; leaves are predictions.
- Search trees (BFS, DFS): the state space explored, rooted at the start state.
- Abstract syntax trees (ASTs): programs as trees in compilers and theorem provers.

Animation — tree grow

Transcript — click a line to jump7 cues

0.0sTrees grow level by level
1.5sRoot R appears at the top
2.5sLevel 1: children A and B sprout, edges connect them to R
3.5sLevel 2: nodes C, D, and E grow under A and B
5.0sLevel 3: F under C, G under D — these are the leaves
6.0sEdges flash cyan one by one to highlight parent-child links
8.5sEach node has at most one parent; every root-to-node path is unique

Well-bracketed structures

A structure (text, program, expression) is well-bracketed when every opening bracket has a matching closing bracket of the right kind, with proper nesting. Examples:

Arithmetic: 3 * (a + 5) — the parentheses around a + 5 match. The expression 3 * a + 5) has an unmatched ).
HTML:


&lt;book&gt;
  &lt;title&gt;SMAI&lt;/title&gt;
  &lt;author&gt;Kohlhase&lt;/author&gt;
&lt;/book&gt;

Every <tag> has a matching </tag>, properly nested.

Python:


if x > 0:
    print("positive")
else:
    print("non-positive")

The if/else blocks are properly nested.

Observation. All well-bracketed structures share a common data structure: a tree. The brackets enclose subtrees; bracket-less 'atoms' are leaves. This insight unifies expressions, markup, and programs.

Trees as the common data structure

Idea (Obs 3.2). A well-bracketed structure consists of either a bracket-less atom, or a bracket enclosing a sequence of well-bracketed sub-structures.

Example 3.3 (HTML → tree):


&lt;book&gt;
  &lt;title&gt;SMAI&lt;/title&gt;
&lt;/book&gt;

Becomes the tree:

book
/   \\
title
 |
SMAI

Every bracket becomes a tree node; bracket-less content becomes a leaf. This same rule applies to:
- Arithmetic: $(2 + 3) * 5$ → product(sum(2, 3), 5).
- Programs: if c then a else b → if-node with three subtrees.
- Markup: any well-bracketed XML/HTML.

Definition 3.4. Such structures — inductively built from atoms and bracketed groups — are precisely the trees.

Worked example

Step 0 of 2

Practice — score 100% to advance

Multiple choice

A tree has how many edges if it has

n

vertices?

The root of a tree has indegree…

A leaf in a tree is…

The height of a tree is…

What kind of tree is used to represent program structure in compilers?

Why must every non-trivial tree have at least one leaf?

Which of these is well-bracketed?

Fill in the blank

A tree on

n

vertices has exactly

n -

edges.

The unique vertex with

\text{indeg} = 0

in a tree is called the ___.

A vertex with no children is called a ___.

Loading…