Algotree > Algorithms > Recursive Algorithms 🌀 🌀 🌀 > Finding the maximum depth of a binary tree

Finding the maximum depth of a binary tree

The maximum depth of a binary tree could easily be found using a simple recursive algorithm.
The maximum depth would be 1 + maximum of ( depth of root’s left subtree or depth of root’s right subtree ).
We continue to use this approach for root node’s left child and root node’s right child to find the maximum depth of their corresponding subrees.

Example : Consider the below binary tree (Tree A) in which the depth is calculated for each node beginning with the leaf nodes. The depth is then returned to the parent node that compares the depth of the left and right subtrees and continues to return the maximum calculated depth to its parent.

Binary_Tree

Below is the algorithm

Algorithm : MaxDepth ( Node root )

1.    If root equals null then
          return 0
2.    Else
3.        return 1 + MaxDepth ( root’s left child, root’s right child ).

C++ program for finding the maximum depth of a binary tree

#include<iostream>

using namespace std;

class Node {
    public:
    int val;
    Node *left;
    Node *right;
    Node() : val(0), left(nullptr), right(nullptr) {}
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
    Node(int x, Node *left, Node *right) : val(x), left(left), right(right) {}
};

class BinTree {

    public:
    int MaxDepth (Node* root) {
        if (root == nullptr) {
            return 0;
        } else {
            return 1 + max(MaxDepth(root->left), MaxDepth(root->right));
        }
    }
};

int main() {

    /*
       30
       / \
      12  20
         /  \
        25   70   
    */

    Node node_25 (25, nullptr, nullptr);
    Node node_70 (70, nullptr, nullptr);
    Node node_12 (12, nullptr, nullptr);
    Node node_20 (20, &node_25, &node_70);
    Node node_30 (30, &node_12, &node_20);

    BinTree t;
    cout << "Max Depth of tree with root " << node_30.val << " : " << t.MaxDepth(&node_30) << endl;

    /*
        1 
       / \
      2   3
         / \
        4   5   
           / \
          6   7
             / \
            8   9  */

    Node node_9 (9, nullptr, nullptr);
    Node node_8 (8, nullptr, nullptr);
    Node node_7 (7, &node_8, &node_9);
    Node node_6 (6, nullptr, nullptr);
    Node node_5 (5, &node_6, &node_7);
    Node node_4 (4, nullptr, nullptr);
    Node node_3 (3, &node_4, &node_5);
    Node node_2 (2, nullptr, nullptr);
    Node node_1 (1, &node_2, &node_3);

    cout << "Max Depth of tree with root " << node_1.val << " : " << t.MaxDepth(&node_1) << endl;

    return 0;
}

Output

Max Depth of tree with root 30 : 3
Max Depth of tree with root 1 : 5