Binary trees are hierarchical data structures where each node has at most two children: a left child and a right child. The depth (or height) of a binary tree represents how many levels of nodes exist from the root down to the deepest leaf.
Thinking about tree depth naturally leads us to recursion - a programming technique where a function calls itself to solve smaller versions of the same problem. Trees are perfect for recursion because every subtree is itself a tree!
To find the depth of any tree, we can break it down into two key insights:
This works because we're essentially asking: "How deep is the deepest path I can take from this node?" The answer is always one step down (the current node) plus whichever subtree goes deeper.
Recursion handles the complexity for us - we don't need to manually traverse every path or keep track of levels. Instead, we trust that our function will correctly calculate the depth of each subtree, then we just combine those results.
The beauty of this approach is its simplicity. Whether the tree has 3 nodes or 3000 nodes, whether it's perfectly balanced or completely lopsided, the same logic applies. Each recursive call works on a smaller problem until we reach the base case of empty subtrees.
1def count_nodes(root):
2 """Count total nodes in a binary tree using recursion"""
3 # Base case: empty tree has 0 nodes
4 if root is None:
5 return 0
6
7 # Recursive case: 1 + nodes in both subtrees
8 left_count = count_nodes(root.left)
9 right_count = count_nodes(root.right)
10
11 return 1 + left_count + right_count