[Recursion]: Finding maximum depth of a binary tree

Recursion in programming is quite common and yet quite tricky to get right. The only you can get it right is by writing code that uses recursion a few times and understand the thinking pattern required to identify smaller version of the same problem.

A typical example of recursion is to find depth of a binary tree.

Say, your tree class looks like following.

public class Node {

    public Node Left { get; set;}

    public Node Right {get; set;}

    public int Value { get; set;}

}

if your tree looks like following, then you can find its maximum depth by just looking at it.

                                                 8

                                          12         15

                                       6    null  null  9

                                                             30

Now, imagine that this tree is much larger. Inspection of the tree is not going to help much. Instead, it might be better to figure out the maximum depth at any given level by 1) looking at depth of its child nodes 2) finding maximum of the depths calculated for its children 3) adding 1 to  it.

So a recursive function that calculates the maximum depth will look like below.

public int FindMaximumDepth(Node node){

    if(node == null){

         return 0;

    }

    var left = FindMaximumDepth(node.Left);

    var right = FindMaximumDepth(node.Right);

    return 1 + Math.Max(left, right);

}

As you can see the above code is quite concise as it uses recursion by finding a smaller version of the same problem by identifying the recursive pattern to the problem. It is quite helpful to have practiced the identification of recursive pattern.