Week 8 — Trees
General and binary trees, traversals (pre/in/post/BFS), Euler tours, and expression-tree case study.
Trees
Definitions, the tree and binary-tree ADTs, linked/array-based representations, traversals, and the template-method Euler tour.
Theory
A tree is a connected acyclic graph with one designated root; depth is the distance from the root, height is the maximum depth among descendants.
Binary trees can be stored in arrays using index 2i+1 (left), 2i+2 (right) — the foundation of array-based heaps.
Traversals: preorder visits parent before children, postorder visits children first, inorder (binary only) visits left → node → right, BFS visits level by level.
An Euler tour traversal is a unifying framework that subsumes pre/in/post order traversals as special cases.
Key points
- Inorder traversal of a BST yields keys in sorted order.
- Tree height bounds the cost of root-to-leaf operations.
- Use a queue for BFS; use recursion (or an explicit stack) for DFS-style traversals.
Code examples
class Node:
def __init__(self, v, left=None, right=None):
self.v, self.left, self.right = v, left, right
def preorder(n):
if n is None: return
yield n.v
yield from preorder(n.left)
yield from preorder(n.right)
def inorder(n):
if n is None: return
yield from inorder(n.left)
yield n.v
yield from inorder(n.right)
def postorder(n):
if n is None: return
yield from postorder(n.left)
yield from postorder(n.right)
yield n.vfrom collections import deque
def level_order(root):
if root is None: return
q = deque([root])
while q:
n = q.popleft()
yield n.v
if n.left: q.append(n.left)
if n.right: q.append(n.right)