Decision Trees#

Q. What is a tree?

Possible answer

A tree is a connected acyclic graph.

Q. What is a graph? connected graph? acyclic graph?

Exercies

What is the amount of different graphs with \(n\) vertices? What about trees?

Hint. Consider \(n=1, 2, 3\) first.

Cayley’s formula

The number of trees with \(n\) vertices is \(n^{n-2}\).

../_images/tree.webp

In binary tree all vertices have no more than two children.

Q. How many nodes can have a binary tree of height \(h\)?