# Tree study problems

### Problem 1

Let's make the following definition:

If T is a binary tree with root r, then its rank is
- 0 if r has no children
- 1+q if r has two children, both with rank q
- otherwise, the maximum rank of any of the children

(a) Compute the rank of each subtree in the following tree:

Hint: for each subtree, write the rank on its root.
Start with the leaf nodes and work upwards in the tree.

Check your
solution before you do parts (b) and (c), to
make sure you correctly understand the definition of rank.

(b) For a given height h, what shape of tree has the largest rank?
smallest rank?

Check your
solution before you do part (c).

(c) Use induction to prove the following claim:

Claim: a tree with rank q has at least \(2^q\) leaves

Check the
outline of your solution.

Check your
full solution.

### Problem 2

Let's define the grammar G as follows:

- Start symbols: S
- Terminals: a
- Rules:
\(S \ \rightarrow \ a \ \mid\ aB \)

\(B \ \rightarrow \ aaS \ \mid\ BB \)

Notice a tree generated by G has a terminal string
of the form \(a^n\) i.e. n copies of the terminal value a.
Prove that n is congruent to 1 (mod 3).

Hint 1: you can handle the modular arithmetic informally.
Concentrate on building a good outline for the tree induction.

Hint 2: let's define the notation L(T) to be the length of the terminal
string of tree T.

Hint 3: you may wish to strengthen the claim, i.e.
modify your grammar and claim to cover a wider
range of trees.
(WTF? Here are some hints.)

Check against the solution.

### Problem 3

A **free tree** is a connected (undirected) graph that contains no cycles.
So it has a tree-like structure, but no root and no left-to-right ordering on
its nodes.
A free tree **spans** a graph G
if it is a subgraph of G and contains all of G's nodes.
It is also called a
** spanning tree** of G,

Let us define a function f as follows:
$$
\begin{equation}
f(n) =
\begin{cases}
1 \quad when \quad n = 0 \\ \\
2^{n-1} (f(n-1))^2 \quad when \quad n \geq 1 \\
\end{cases}
\end{equation}
$$

Prove that for any hypercube \(Q_{n}\) (\(n \geq 0\)) there are at least
f(n) distinct free trees that span \(Q_{n}\).

Stuck? Here are some hints.

Check against the solution.

### Problem 4

Flatlander Chocolates makes rectangular chocolate bars, each
divided into a p by q grid of squares. We can break a
chocolate bar in two along one of the grid lines. Prove
that it takes pq-1 breaks to divide a chocolate bar into
individual squares.

Stuck? Here are some hints.

Check against the solution.