Trees: Recursive Thinking for Hierarchical Data

Trees are the first data structure where recursion often feels like the simplest solution rather than an optional trick. A tree node has smaller trees beneath it. That means many tree methods solve the left subtree, solve the right subtree, and combine the results.

A binary tree node

class TreeNode
{
    private int value;
    private TreeNode left;
    private TreeNode right;

    public int getValue() { return value; }
    public TreeNode getLeft() { return left; }
    public TreeNode getRight() { return right; }
}

Worked example: height

The height of a tree is the length of the longest downward path. The recursive idea is: the height is one plus the larger height of the two subtrees.

public static int height(TreeNode root)
{
    if (root == null)
        return 0;

    int leftHeight = height(root.getLeft());
    int rightHeight = height(root.getRight());

    return 1 + Math.max(leftHeight, rightHeight);
}

If a node has no children, both recursive calls return 0, so the leaf height is 1. This is a clean example of the base case giving meaning to every later return.

Traversal order changes the output

For this tree:

      10
     /  \
    5    18
   / \     \
  2   7     20

Traversal	Order	Use
Preorder	10, 5, 2, 7, 18, 20	Copying or printing structure from the root outward.
Inorder	2, 5, 7, 10, 18, 20	Sorted output for a binary search tree.
Postorder	2, 7, 5, 20, 18, 10	Deleting or evaluating children before a parent.

Binary search tree lookup

A binary search tree uses order to avoid searching both sides.

public static boolean contains(TreeNode root, int target)
{
    if (root == null)
        return false;

    if (target == root.getValue())
        return true;
    if (target < root.getValue())
        return contains(root.getLeft(), target);

    return contains(root.getRight(), target);
}

This can be efficient when the tree is balanced. If the tree is badly unbalanced, it can behave like a linked list.

Practice prompt

Write countLeaves(TreeNode root). A leaf is a non-null node whose left and right children are both null. Then trace your method on the tree shown above.