How to find the maximum depth of a binary tree

The maximum depth of a binary tree is the number of nodes from the root node to the farthest leaf node. The maximum depth of a binary tree also called as the height of a binary tree.

Let's see an example.  

binary tree

 

What is the maximum depth of the binary tree? Based on the definition: is the number of nodes from the root node to the farthest leaf node. The tree has two farthest the root to the leaf paths:

  • 1 -> 3 -> 7
  • 1 -> 3 -> 6

Each path has three nodes, so the maximum depth or height of a binary tree equals three.

 

binary tree

Algorithm

To count the maximum depth we can use recursion:

  • Recursively calculate the height of the binary tree to the left of the root
  • Recursively calculate the height of the binary tree to the right of the root
  • Take the maximum value from the heights of the left and right subtrees and add one, to account the root node

 

binary tree

Code

    public int MaxDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = MaxDepth(root.Left);
        int right = MaxDepth(root.Right);
        return Math.Max(left, right) + 1;
    }

Time Complexity: O(n)