Trees and Networks

Trees and Networks

---

Definitions

---

Properties of Trees

---

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

---

Applications in AI/ML

---

Common Mistakes

---

Interview Questions

1. 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.

2. 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).

3. 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.

4. 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)$.

5. 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.

6. 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.

7. 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.

8. 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

---

Quick Reference

---

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