Tree Algorithms
Trees organize data by parent-child relationships and support fast search, traversal, and hierarchy processing.
Algorithm Use Complexity
DFS Traversal Visit all nodes deeply first. O(n)
BFS / Level Order Visit level by level. O(n)
BST Search Search using left < node < right. O(h), balanced O(log n)
Key vocabulary
- Root: top node.
- Leaf: node with no children.
- Height: longest path from a node to a leaf.
- Subtree: a tree inside a tree.
DFS traversal patterns
preorder(node): visit, left, right
inorder(node): left, visit, right
postorder(node): left, right, visit
Useful tree algorithms
- Find height or depth.
- Check if a tree is balanced.
- Find lowest common ancestor.
- Use heaps for priority queues.
- Use tries for prefix search.
Common mistakes
- Confusing tree height and depth.
- Forgetting null/empty child checks.
- Assuming a normal binary tree is automatically a binary search tree.
Practice
- Draw preorder, inorder, and postorder for a small tree.
- Search for 17 in a BST and list visited nodes.
- Explain why a balanced BST is faster than a linked list.
Study tip: learn the idea first, trace one small example by hand, then code it.
Computer Algorithms Quick Guide - Tree Algorithms