<aside> 📚

L5: Make Friends with Trees covers trees in general (definition, terminology), binary trees (structure, node counts, expression trees), implementing binary trees in Java (Node class with left/right/parent), binary search trees (recursive definition, search, inorder traversal, non-recursive traversal with stack), implementing sets with BSTs, the Comparable interface, and tree iterators.

</aside>

📋 At a Glance

• [ ] Understand the mathematical definition of a tree (acyclic undirected graph)
• [ ] Know tree terminology: root, parent, child, leaf, level, height, subtree
• [ ] Know binary tree node counts: 2^l at level l, 2^h - 1 total for height h
• [ ] Implement the Node<T> class and BinaryTree<E> class in Java
• [ ] Define a binary search tree recursively and understand the BST property
• [ ] Implement getNode, contains, and add for a BST in Java
• [ ] Write recursive and non-recursive inorder tree walks
• [ ] Understand the tree iterator (successor-finding rules)
• [ ] Know that BSTs implement the Set ADT with no duplicates

<aside> 📅

Week 9 Feb (w/c 9 Feb) — Lecture 5 of 26 | Tutorial 3 applies

</aside>

<aside> 💡

Key principle: Binary search trees keep elements ordered so that search follows a single path from root to leaf. The worst-case number of comparisons equals the height of the tree — a balanced tree gives O(log n) search, but an unbalanced one degrades to O(n).

</aside>

1. Trees: Definition and Terminology

Mathematically, a tree is an acyclic undirected graph:

• Graph: a structure of nodes (vertices) joined by edges
• Undirected: edges have no direction
• Acyclic: there are no cycles