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)

Popular articles


How to reverse a linked list In this tutorial, you will see how to implement a reverse linked list algorithm.
Valid parentheses In this tutorial, you will see how to use the stack data structure to validate parentheses.
Find the missing number In this article, you will know how to find the missing number.
How to count the height of a binary tree The height of the binary tree is the number of edges in the longest path from the root node to a leaf node.
How to find bottom left value in a binary tree The naive approach, visit all nodes and compare a value in each node. A better approach is to use the definition of a binary search tree.
Binary tree postorder traversal without recursion We have seen preorder traversal algorithm for a binary tree with recursion. In this article, we'll implement postorder traversal algorithm for a binary tree without recursion
Binary tree inorder traversal without recursion We have seen inorder traversal algorithm for a binary tree, but it was a recursive version. In this article, we'll take a look at the non-recursive approach
How to check if two binary trees are the same Given two binary trees, write a method to check if the trees are the same or not