Trees appear whenever data has hierarchy: folders, tournament brackets, family-style relationships, decision paths, and expression structures. A tree node can have children, and those children can have their own children.
Core vocabulary
- Root: the top node.
- Leaf: a node with no children.
- Height: how far the tree extends downward.
- Subtree: a smaller tree inside the larger tree.
Why recursion fits
A tree is naturally recursive because each child can be viewed as the root of a smaller tree. Many tree algorithms ask the same question about the left subtree and the right subtree, then combine the results.
public int countNodes(TreeNode node)
{
if (node == null)
return 0;
return 1 + countNodes(node.getLeft()) + countNodes(node.getRight());
}Traversal order matters
Preorder visits the node before children. Inorder visits left, node, right. Postorder visits children before the node. Students should always ask what order the problem needs before writing traversal code.
Common mistakes
- Forgetting the null base case.
- Confusing a leaf with a null reference.
- Using the wrong traversal order.
- Returning only one subtree's answer when both are needed.