So far, our data structures have been either linear (arrays, linked lists, stacks, queues - one element after another) or hash-based (hash maps and sets - instant lookup by value). Both arrange data on a flat plane.
But real-world data is often hierarchical. Your file system has folders inside folders. A company has managers who manage managers who manage employees.
A tree is the data structure for this. It's a collection of nodes, where each node has a value and children - forming a branching structure.
Trees introduce two big ideas you'll carry through the rest of the course:
A tree has a root node at the top. Each node has a value and children. Nodes with no children are called leaves.
Two common tree types:
| Operation | BST (balanced) | BST (skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Traverse | O(n) | O(n) |
Visit every node of this binary search tree in a specific traversal order.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
// DFS Traversals (recursive)
void Inorder(TreeNode node) { // left -> root -> right
if (node == null) return;
Inorder(node.left);
Console.Write(node.val + " ");
Inorder(node.right);
}
void Preorder(TreeNode node) { // root -> left -> right
if (node == null) return;
Console.Write(node.val + " ");
Preorder(node.left);
Preorder(node.right);
}
void Postorder(TreeNode node) { // left -> right -> root
if (node == null) return;
Postorder(node.left);
Postorder(node.right);
Console.Write(node.val + " ");
}
// BFS (Level order)
void LevelOrder(TreeNode root) {
var q = new Queue<TreeNode>();
q.Enqueue(root);
while (q.Count > 0) {
var node = q.Dequeue();
Console.Write(node.val + " ");
if (node.left != null) q.Enqueue(node.left);
if (node.right != null) q.Enqueue(node.right);
}
}BST property: left.val < node.val < right.val for ALL nodes (not just immediate children).
This property enables fast search - in a balanced tree, at each node you eliminate roughly half the remaining nodes.
// BST Search - O(log n) average
TreeNode Search(TreeNode root, int target) {
while (root != null) {
if (root.val == target) return root;
root = target < root.val ? root.left : root.right;
}
return null;
}
// BST Insert - O(log n)
TreeNode Insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = Insert(root.left, val);
else root.right = Insert(root.right, val);
return root;
}
// Validate BST - O(n)
bool IsValidBST(TreeNode root) {
return Validate(root, long.MinValue, long.MaxValue);
}
bool Validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return Validate(node.left, min, node.val)
&& Validate(node.right, node.val, max);
}Trees are the right choice when:
Trees vs other structures:
| Structure | Use when |
|---|---|
| Array / List | Flat, ordered data with index access |
| Hash map | Key-value lookup (no ordering needed) |
| Tree | Hierarchical OR needs sorted order OR range queries |
| Graph (Module 10) | No hierarchy, arbitrary connections |
When NOT to use a tree:
Decision guide:
| Signal | Structure |
|---|---|
| "Sorted order of keys" | BST |
| "Find all values in range" | BST |
| "Hierarchy / parent-child" | Tree |
| "Fast lookup, no order needed" | Hash set/map |
| "Relationships between items" | Graph (Module 10) |
BST validation: checking only immediate children: A common mistake: left.val < node.val < right.val. This is WRONG. ALL nodes in the left subtree must be < node.val. Example: root=5, left=3, left.right=6 would pass the naive check but violates BST (6 > 5). Use the min/max range approach.
Forgetting null checks on tree nodes: node.left and node.right can be null. Always check if (node == null) return before accessing children.
Recursion depth in skewed trees: A tree with n nodes can be n levels deep if it's skewed (basically a linked list). Recursive traversal uses O(n) stack space and risks overflow. Consider iterative traversal for worst-case trees.
A trie (prefix tree) stores strings in a tree where each node represents a character. This is a more advanced topic. Make sure you are comfortable with trees and hash maps first.
Used for autocomplete, spell check, and IP routing.
| Operation | Trie |
|---|---|
| Insert | O(m) where m = word length |
| Search | O(m) |
| Prefix search | O(m) |
Space: O(total characters across all words).
public class TrieNode {
public Dictionary<char, TrieNode> children = new();
public bool isEnd = false;
}
public class Trie {
private readonly TrieNode root = new();
public void Insert(string word) {
var node = root;
foreach (char c in word) {
if (!node.children.ContainsKey(c))
node.children[c] = new TrieNode();
node = node.children[c];
}
node.isEnd = true;
}
public bool Search(string word) {
var node = Find(word);
return node != null && node.isEnd;
}
public bool StartsWith(string prefix) {
return Find(prefix) != null;
}
private TrieNode Find(string s) {
var node = root;
foreach (char c in s) {
if (!node.children.TryGetValue(c, out node))
return null;
}
return node;
}
}Trees introduced you to hierarchical data and recursive traversal. A tree has a strict parent-child relationship - each node (except the root) has exactly one parent.
So far, every algorithm you've learned explores all possibilities or follows a fixed rule. But what if you could solve a problem by simply making the best choice at each step? That's the idea behind Greedy Algorithms - and it works for a surprising number of problems, from interval scheduling to stock trading.
If trees are about navigating hierarchy, greedy algorithms are about trusting your instincts.
Next up: Greedy & Intervals