Trees and Networks

Why It Matters

Trees are the most important special case of graphs. They model hierarchical structures (file systems, organizational charts), enable efficient search (binary search trees, B-trees), represent parsing (syntax trees in compilers), and optimize networks (spanning trees in routing). Every connected acyclic graph is a tree, and trees appear in data structures, algorithms, databases, and network design throughout computer science.

Definitions

DfTree

A tree is a connected acyclic graph. Equivalently, a tree is a graph with $n$ vertices and exactly $n - 1$ edges that contains no cycles.

DfRooted Tree

A rooted tree is a tree with a designated root vertex. Every other vertex has a unique parent and zero or more children. The root has no parent.

DfLeaf

A leaf (or external node) is a vertex with degree 1 in an unrooted tree, or a vertex with no children in a rooted tree.

DfInternal Node

An internal node is a non-leaf vertex. In a rooted tree, it has at least one child.

DfBinary Tree

A binary tree is a rooted tree where each vertex has at most two children, called left child and right child.

DfFull Binary Tree

A full binary tree is a binary tree where every internal node has exactly two children.

DfComplete Binary Tree

A complete binary tree is a binary tree where every level is completely filled except possibly the last level, which is filled from left to right.

DfHeight

The height of a tree is the length of the longest path from the root to a leaf. A tree with one vertex has height 0.

DfDepth

The depth of a vertex is the length of the path from the root to that vertex. The root has depth 0.

DfSpanning Tree

A spanning tree of a connected graph $G$ is a subgraph that is a tree and includes all vertices of $G$ .

DfMinimum Spanning Tree (MST)

A minimum spanning tree of a weighted graph is a spanning tree with the minimum total edge weight.

Properties of Trees

ThFundamental Properties of Trees

For a tree with $n$ vertices:

The tree has exactly $n - 1$ edges
There is exactly one path between any two vertices
Adding any edge creates exactly one cycle
Removing any edge disconnects the tree
A tree is maximally acyclic and minimally connected

ThCayley's Formula

The number of distinct spanning trees of the complete graph $K_n$ is $n^{n-2}$ .

ThCenter of a Tree

Every tree has either one center vertex or two adjacent center vertices. The center is found by repeatedly removing leaves until 1 or 2 vertices remain.

Python Implementations

Tree Class and Traversals

from collections import defaultdict, deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = []

    def add_child(self, child):
        self.children.append(child)

class Tree:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)
        self.root = None

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def is_tree(self):
        if self.n == 0:
            return True
        visited = set()
        queue = deque([0])
        visited.add(0)
        while queue:
            node = queue.popleft()
            for neighbor in self.graph[node]:
                if neighbor in visited:
                    return False
                visited.add(neighbor)
                queue.append(neighbor)
        return len(visited) == self.n

    def bfs(self, start=0):
        visited = set()
        queue = deque([start])
        visited.add(start)
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return order

    def find_leaves(self):
        return [v for v in range(self.n) if len(self.graph[v]) == 1]

    def height(self, root=0):
        visited = set()
        queue = deque([(root, 0)])
        visited.add(root)
        max_h = 0
        while queue:
            node, h = queue.popleft()
            max_h = max(max_h, h)
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, h + 1))
        return max_h

t = Tree(6)
for u, v in [(0,1), (0,2), (1,3), (1,4), (2,5)]:
    t.add_edge(u, v)

print(f"Is tree: {t.is_tree()}")
print(f"BFS: {t.bfs()}")
print(f"Leaves: {t.find_leaves()}")
print(f"Height: {t.height()}")

Binary Search Tree

class BSTNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = BSTNode(val)
        else:
            self._insert(self.root, val)

    def _insert(self, node, val):
        if val < node.val:
            if node.left is None:
                node.left = BSTNode(val)
            else:
                self._insert(node.left, val)
        else:
            if node.right is None:
                node.right = BSTNode(val)
            else:
                self._insert(node.right, val)

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)

    def height(self):
        return self._height(self.root)

    def _height(self, node):
        if node is None:
            return -1
        return 1 + max(self._height(node.left), self._height(node.right))

bst = BST()
for val in [5, 3, 7, 1, 4, 6, 8]:
    bst.insert(val)

print(f"Inorder: {bst.inorder()}")
print(f"Search 4: {bst.search(4) is not None}")
print(f"Height: {bst.height()}")

Minimum Spanning Tree (Kruskal's Algorithm)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal_mst(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total_weight += w
            if len(mst) == n - 1:
                break
    return mst, total_weight

edges = [(0,1,4), (0,2,3), (1,2,1), (1,3,2), (2,3,5)]
mst, weight = kruskal_mst(4, edges)
print(f"MST edges: {mst}")
print(f"Total weight: {weight}")

Spanning Tree Algorithms

ThPrim's Algorithm

Start from any vertex. Repeatedly add the minimum weight edge connecting a tree vertex to a non-tree vertex. Runs in $O(E \log V)$ with a priority queue.

ThKruskal's Algorithm

Sort all edges by weight. Add edges in order if they don't create a cycle (checked via Union-Find). Runs in $O(E \log E)$ .

Applications in AI/ML

Applications in AI and Machine Learning

Decision Trees: Split data on features to classify or predict; Random Forests and Gradient Boosting ensembles
Syntax Trees: Parse sentences in NLP; abstract syntax trees in code generation
Huffman Coding: Optimal prefix-free codes for compression based on frequency trees
Spanning Trees: Network routing protocols (STP in Ethernet) use minimum spanning trees
Hierarchical Clustering: Build dendrograms (trees) showing data groupings at different levels
Knowledge Graphs: Ontology hierarchies form tree structures
Search Trees: B-trees and B+ trees in databases; game trees in AI (minimax)

Common Mistakes

Mistake	Correction
Confusing "tree" with "binary tree"	A general tree has no restriction on the number of children per node
Forgetting trees have exactly $n-1$ edges	A connected graph with $n$ vertices and $n$ edges has exactly one cycle
Assuming all binary trees are BSTs	A BST must satisfy the ordering property: left < root < right
Confusing full, complete, and perfect	Full: 0 or 2 children; Complete: filled left to right; Perfect: all leaves at same depth
Not handling empty trees	An empty graph (0 vertices) is technically a tree
Confusing height and depth	Height is max depth; depth is distance from root to a specific node
Forgetting MST uniqueness	MST is unique only if all edge weights are distinct
Assuming Kruskal's needs a specific start	Kruskal's is edge-based; Prim's is vertex-based

Interview Questions

What are the properties of a tree? A tree with $n$ vertices has $n-1$ edges, is connected, and is acyclic. There is exactly one path between any pair of vertices.
How do you check if a graph is a tree? Verify it has $n-1$ edges and is connected (BFS/DFS reaches all vertices without finding a cycle).
What is the difference between Prim's and Kruskal's? Prim's grows from a vertex using a priority queue; Kruskal's processes sorted edges using Union-Find. Both produce the same MST weight.
What is a BST and what is its height? A BST orders data so left < root < right. Average height is $O(\log n)$ ; worst case (sorted input) is $O(n)$ .
How do you find the lowest common ancestor (LCA)? In a BST, LCA is where the two nodes diverge. In a general tree, use binary lifting or Euler tour with RMQ.
What is tree balancing and why does it matter? AVL and Red-Black trees maintain $O(\log n)$ height through rotations, preventing worst-case $O(n)$ degradation.
How does a spanning tree relate to network design? A minimum spanning tree connects all nodes with minimum total cable cost, used in network infrastructure design.
What is the center of a tree? The center is found by repeatedly peeling leaves. Every tree has 1 or 2 center vertices that minimize the maximum distance to all other vertices.

Practice Problems

Practice: Cayley's Formula

Problem: How many spanning trees does $K_4$ (complete graph on 4 vertices) have?

Solution: Cayley's Formula

By Cayley's formula: $n^{n-2} = 4^{4-2} = 4^2 = 16$ spanning trees.

Practice: BST Height

Problem: What is the height of a BST containing the elements 1, 2, 3, 4, 5, 6, 7 in order of insertion?

Solution: BST Height

Inserting sorted elements into a BST produces a degenerate (linked list) tree with height $n - 1 = 6$ .

Practice: Spanning Tree Count

Problem: A graph has vertices {0, 1, 2, 3} and edges {(0,1), (0,2), (1,2), (1,3), (2,3)}. How many spanning trees does it have?

Solution: Spanning Tree Count

Using the matrix tree theorem or enumeration: the spanning trees are {(0,1),(1,2),(2,3)}, {(0,1),(1,2),(0,2)}, {(0,1),(0,2),(2,3)}, {(0,1),(1,3),(2,3)}, {(0,2),(1,3),(1,2)}, {(0,2),(1,3),(2,3)}. Total: 8 spanning trees.

Practice: MST Weight

Problem: Find the MST weight for a graph with edges: (0,1,2), (0,2,3), (1,2,1), (1,3,4), (2,3,5).

Solution: MST Weight

Sort edges: (1,2,1), (0,1,2), (0,2,3), (1,3,4). Kruskal's: add (1,2,1), (0,1,2), then (0,2,3) creates cycle. Add (1,3,4). MST weight = 1 + 2 + 4 = 7.

Quick Reference

Concept	Formula/Description
Edges in tree	$n - 1$
Leaves in full binary tree	$i + 1$ where $i$ is internal nodes
Height of balanced BST	$O(\log n)$
Height of degenerate BST	$O(n)$
Cayley's formula	$n^{n-2}$ spanning trees for $K_n$
Kruskal's complexity	$O(E \log E)$
Prim's complexity	$O(E \log V)$
BST search	$O(\log n)$ average, $O(n)$ worst
Inorder traversal	Left, Root, Right (sorted for BST)
BFS on tree	Level-order traversal

Cross-References

Graph Theory -> 074-discrete-graphs.mdx: Trees are connected acyclic graphs; graph algorithms apply
Recurrence Relations -> 076-discrete-recurrence.mdx: Tree height satisfies recurrences; divide-and-conquer on trees
Number Theory -> 077-discrete-number-theory.mdx: Cayley's formula connects to combinatorics
Boolean Algebra -> 078-discrete-boolean.mdx: Binary decision trees use Boolean conditions
Automata Theory -> 079-discrete-automata.mdx: Parse trees and syntax trees in formal languages
Applications -> 080-discrete-applications.mdx: Trees in databases, networks, and algorithms

Trees and Networks