Recursion, binary trees, and a note on debugging

Recursion started to feel natural this week after spending time manually tracing call stacks for small inputs. The mechanical understanding — “this frame waits while that frame resolves” — preceded the intuitive understanding, which I think is the correct order.

Binary tree traversals

Implemented in-order, pre-order, and post-order traversals both recursively and iteratively. The recursive versions are trivially concise. The iterative versions require explicit stack management and are more instructive for understanding what the runtime actually does.

In-order traversal of a BST yields sorted output, which is a useful property for validation: if your in-order traversal isn’t sorted, your tree invariant is broken.

On debugging recursive functions

print statements are inadequate for debugging recursion because the output is a flat list that doesn’t represent the call hierarchy. What works better: adding an indent parameter that increments with depth, so each recursive call prints with increasing indentation. The visual structure of the output mirrors the call tree.

def traverse(node, depth=0):
    if not node:
        return
    prefix = "  " * depth
    print(f"{prefix}{node.val}")
    traverse(node.left, depth + 1)
    traverse(node.right, depth + 1)

Small technique, large improvement in comprehension.