Trees

Definition and Basic Properties

Graph-Theoretic Definition

Tree: connected, undirected graph with no cycles. Equivalent: connected acyclic graph. Order: number of vertices (n). Size: number of edges (n-1).

Acyclicity

No simple cycles. Guarantees unique simple paths between vertices. Cycle presence → not a tree.

Connectivity

Every pair of vertices connected by a path. Removal of any edge disconnects the graph (bridge).

Edges and Vertices Relationship

Edges count always one less than vertices: |E| = |V| - 1. Fundamental property used in proofs and algorithms.

Characterizations

Equivalent statements: (1) connected, acyclic, (2) acyclic with |E|=|V|-1, (3) connected with |E|=|V|-1, (4) unique path between any two vertices.

Types of Trees

Unrooted Trees

No designated root. Used in network topology, phylogenetics.

Rooted Trees

One vertex designated root. Imposes parent-child hierarchy. Basis for rooted subtree, levels, height.

Binary Trees

Each vertex has at most two children (left, right). Basis for binary search trees, heaps.

Spanning Trees

Subtrees that include all vertices of a graph. Used in optimization and connectivity problems.

Ordered Trees

Children of each vertex ordered. Used in parsing, XML document structure.

Key Properties

Number of Edges

Edges = vertices - 1. Basis for tree recognition and construction.

Unique Paths

Exactly one simple path between any two vertices. No ambiguity in traversal.

Leaf and Internal Vertices

Leaf: vertex with degree 1. Internal: degree ≥ 2 (except root in rooted trees).

Diameter

Longest shortest path between any two vertices. Measures "width" of a tree.

Height and Depth

Height: max distance from root to leaf. Depth: distance from root to vertex.

Representations of Trees

Adjacency List

List of neighbors for each vertex. Efficient for sparse trees.

Adjacency Matrix

n×n matrix with entries 1 or 0 for edges. Space-expensive, simpler for dense graphs.

Parent Array

Array storing parent of each vertex (root’s parent = null). Useful for rooted trees.

Edge List

List of pairs representing edges. Simple but less efficient for certain operations.

Recursive Structures

Recursive definitions for rooted trees: node with subtrees as children.

Spanning Trees

Definition

Subgraph including all vertices and minimal edges forming a tree.

Minimum Spanning Tree (MST)

Spanning tree with minimum total edge weight. Important in network design.

Algorithms

Kruskal’s and Prim’s algorithms for MST construction.

Number of Spanning Trees

Kirchhoff’s Matrix-Tree theorem calculates count of spanning trees.

Applications

Network optimization, clustering, approximation algorithms.

Rooted Trees

Definition

Tree with one vertex designated as root. Defines parent-child relations.

Levels and Depth

Level: distance from root. Depth of root = 0. Levels increase with distance.

Subtrees

Tree formed by a node and all its descendants.

Height

Maximum level among all vertices.

Traversal Methods

Preorder, inorder, postorder traversals used in algorithms and data structures.

Binary Trees

Definition

Rooted tree where each node has ≤ 2 children: left and right.

Types

Full, complete, perfect, balanced binary trees. Differ in node arrangement and completeness.

Binary Search Trees (BST)

Ordered binary trees supporting efficient search, insertion, deletion.

Traversal

Inorder, preorder, postorder critical for processing nodes.

Applications

Databases, expression parsing, priority queues (heaps).

Algorithms on Trees

Traversal Algorithms

DFS, BFS adapted for trees; linear time complexity O(n).

Lowest Common Ancestor (LCA)

Finds shared ancestor of two nodes. Algorithms: binary lifting, Euler tour.

Tree Diameter

Two BFS traversals or DP methods to find longest path.

Dynamic Programming on Trees

Used for optimization problems like subtree sums, independent sets.

Tree Decomposition

Breaking graph into tree-like structures for algorithmic efficiency.

Applications

Computer Science

Data structures, database indexing, syntax trees, network routing.

Network Design

Spanning trees minimize wiring, cost, improve robustness.

Biology

Phylogenetic trees represent evolutionary relationships.

Mathematics

Enumeration, combinatorics, proof techniques.

Artificial Intelligence

Decision trees for classification and regression.

Computational Complexity

Recognition

Checking if graph is a tree: O(n + m) using DFS or BFS.

Construction

Spanning tree algorithms: Kruskal’s and Prim’s run in O(m log n).

Traversal

DFS, BFS linear in number of vertices and edges: O(n).

Advanced Algorithms

LCA preprocessing in O(n log n), queries in O(1).

Optimization Problems

NP-complete problems often simplified on tree structures.

Comparative Table of Tree Types

Examples and Illustrations

Simple Tree Example

Graph with vertices {A, B, C, D}, edges {(A-B), (B-C), (B-D)}: connected, acyclic, 4 vertices, 3 edges.

Rooted Tree Representation

Root: A; children: B; B’s children: C, D.

Binary Tree Example

Root node with left child B, right child C; B with left child D.

Spanning Tree in a Weighted Graph

Graph of 5 vertices and weighted edges; MST found using Prim’s algorithm minimizing total weight.

Algorithmic Pseudocode: Kruskal’s Algorithm

Initialize forest F with each vertex as a separate treeSort edges E by increasing weightFor each edge e in E: If e connects two different trees in F: Add e to F (merge trees)Return F as MST

References

• West, D. B., Introduction to Graph Theory, Prentice Hall, 2nd ed., 2001, pp. 120-160.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C., Introduction to Algorithms, MIT Press, 3rd ed., 2009, pp. 601-650.
• Diestel, R., Graph Theory, Springer, 5th ed., 2017, pp. 75-110.
• Kleinberg, J., Tardos, É., Algorithm Design, Pearson, 2005, pp. 530-565.
• Tarjan, R. E., Data Structures and Network Algorithms, SIAM, 1983, pp. 150-190.