Trees and their properties
A tree is a connected graph with no cycles. Trees organise file systems, family histories, decisions, and data in computers.
Definition
A tree is a connected graph containing no cycles. Equivalently, there is exactly one path between any two vertices. A forest is a graph whose components are trees. Trees are the simplest connected graphs: remove any edge and the graph falls apart; add any edge and a cycle appears.
The edge count
Every tree with \(n\) vertices has exactly \(n - 1\) edges. This can be proved by induction: every tree with at least two vertices has a leaf (a vertex of degree 1), and removing it leaves a tree with one fewer vertex and one fewer edge. Conversely, a connected graph with \(n\) vertices and \(n - 1\) edges is a tree.
|E| = |V| - 1Rooted trees
Choosing one vertex as the root gives a rooted tree, drawn with the root at the top. Each vertex except the root has a parent; vertices below are its children; vertices with no children are leaves. The depth of a vertex is its distance from the root, and the height of the tree is the largest depth.
Binary trees
In a binary tree each vertex has at most two children, called left and right. A full binary tree of height \(h\) has at most \(2^{h+1} - 1\) vertices, so a tree holding \(n\) items needs height at least about \(\log_2 n\). This logarithmic height is why tree-based data structures are fast.
n \le 2^{h+1} - 1Binary search trees
A binary search tree keeps every left descendant smaller and every right descendant larger than each vertex. Searching compares with the root and moves left or right, so a balanced tree with a million items needs only about 20 comparisons. Balanced variants such as AVL and red-black trees keep the height logarithmic as items are added.
Tree traversals
Preorder visits a vertex before its subtrees, inorder visits the left subtree, the vertex, then the right subtree, and postorder visits subtrees first. An inorder traversal of a binary search tree lists the items in sorted order. Expression trees evaluated in postorder compute arithmetic expressions.
Counting trees
Cayley's formula states there are \(n^{n-2}\) labelled trees on \(n\) vertices: 3 on 3 vertices, 16 on 4. The number of binary tree shapes with \(n\) vertices is the Catalan number \(C_n\), connecting trees to the counting unit.
Applications
File systems are rooted trees of folders. Decision trees guide diagnoses and power many machine learning models. Huffman coding builds a binary tree from symbol frequencies to compress data, giving short codes to common symbols. Phylogenetic trees describe evolutionary relationships.
Key takeaways
Trees are connected and acyclic, with exactly one path between vertices and \(n - 1\) edges. Rooted and binary trees organise hierarchical data; logarithmic height makes searches fast. Traversals visit vertices in systematic orders, and inorder on a search tree gives sorted output.
Flashcard
Connected graph with no cycles
Check your understanding
How many edges does a tree with 25 vertices have?