Recursive Algorithms on Trees and Lists

Why trees and recursion belong together. A binary tree is defined recursively: it is either empty, or a node with a left subtree and a right subtree, each of which is itself a binary tree. Any algorithm on a tree therefore has the same shape as the definition. Handle the empty case (the base case), then do something with the node and call yourself on the two subtrees. Iteration can do the same work only by managing its own stack of nodes still to visit, which is longer and more error-prone; recursion lets the call stack do that bookkeeping for free.

The template and its variations. HEIGHT(NODE): if NODE is null return 0; otherwise return 1 + the larger of HEIGHT(left) and HEIGHT(right). Almost every tree question changes only the last line. COUNT: 1 + COUNT(left) + COUNT(right). SUM: value + SUM(left) + SUM(right). LEAVES: return 0 for null, 1 when both children are null, otherwise LEAVES(left) + LEAVES(right). Searching a binary search tree is the one case that visits only one subtree: compare the target with the node's value, and recurse left if smaller, right if larger, stopping on a match or on null. The three traversals — pre-order, in-order, post-order — are the same recursion with the visit placed before, between or after the two recursive calls, and in-order on a binary search tree outputs values in sorted order.

Order of execution and the call stack. Recursive calls go down to the leaves first; values come back up afterwards, and a parent cannot return until both children have. The call stack is as deep as the tree is high: a balanced tree of 1 000 nodes is about 10 levels deep, a degenerate tree (values inserted in sorted order) is 1 000 deep, and a tree deep enough overflows the stack — which is why the same recursive sum that is elegant on a balanced tree can crash on a sorted-input tree. Recursion on a linked list has the same shape: the base case is the null pointer, and each call handles one node then recurses on the rest; but because a list of N items gives N nested calls, a loop is usually preferred for lists and recursion is reserved for trees.

Tracing recursion in the exam. Write each call on its own line with its argument, indent nested calls, and write the returned value beside the call once it is known. Never trace only the final answer: marks are for showing the base cases returning and the values combining on the way up. Two errors account for most lost marks: forgetting the base case (the function calls itself forever) and combining the results wrongly (adding heights instead of taking the maximum).