Tree

A tall plant that lives a long time.

A tree is a connected graph with no cycles. One of its vertices is designated to be the root. If not, then it's a free tree instead of a rooted tree. A group of trees is a forest.

If you add an edge to a tree, a cycle is created. If you remove an edge from a tree, it's disconnected.

Trees pop up in many algorithms because they're great at representing decisions that branch off into several outcomes. The solution to a certain problem may be cleverly equated to traversing a tree in a particular way.

Trees are also good for visualizing the steps of a recursive algorithm.

When you play a game against a computer player, it may be the case that its artificial intelligence is based on a decision tree program that analyzes the state of the game to optimize strategy, even considering probabilities when there's luck involved. However, playing too many steps ahead can still be computationally difficult so the decision tree may have a cap on its height.

Contents

Uniqueness of paths

Here's a super-important property about trees... don't forget it! For any $2$ vertices in a tree, there is exactly $1$ path between them. Therefore, for any $2$ vertices in a tree, there is only $1$ way to travel between them. That path connecting them is unique.

Let $T = (V, E)$ be a tree, with $v, w \in V.$ Then, there is only $1$ path connecting $v$ and $w.$

Number of edges

It is true for every tree that the number of edges is exactly $1$ fewer than the number of vertices.

Let $T = (V, E)$ be a tree. Then: $$|E| = |V| - 1$$

Rooted tree

Rooted trees are typically drawn with the root at the top and all other vertices are organized into lower levels, each defined by their distance from the root. The distance between two vertices is defined as the number of edges in the shortest path between them. The height of a rooted tree is simply the greatest distance any vertex has from the root.

Let's talk a bit about the vertices in a rooted tree. Every non-root vertex in a rooted tree has exactly $1$ parent (of which it is a child), which is the unique vertex that is visited immediately after it in a path to the root. All the vertices that come after a non-root vertex in a path to the root are its ancestors (of which it is a descendant). Rooted trees are drawn such that ancestors appear above their descendants. A vertex without children is a leaf. A vertex without a parent is the root. Vertices with the same parent are siblings.

A subtree is a rooted tree contained entirely within another rooted tree. To build a subtree, pick any vertex in a rooted tree. That vertex and all its descendants together make up a new rooted tree, rooted at the vertex that was picked.

Free tree

A vertex in a free tree is a leaf if its degree is $1.$ Also, when a free tree consists of a single vertex, that vertex is a leaf. A vertex in a free tree is internal if its degree is $\geq 2.$

Here's a statement you might find useful. Any free tree with at least $2$ vertices has at least $2$ leaves:

Let $T = (V, E)$ be a free tree such that $|V| \geq 2.$ Then, the number of leaves in $T$ is at least $2.$

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort