Related Tags

maximum depth
binary tree
recursion

# Finding the maximum depth of a binary tree Educative Answers Team

The maximum depth of a binary tree is the number of nodes from the root down to the furthest leaf node. In other words, it is the height of a binary tree.

Consider the binary tree illustrated below: The maximum depth, or height, of this tree is $4$; node $7$ and node $8$ are both four nodes away from the root.

## Algorithm

The algorithm uses recursion to calculate the maximum height:

1. Recursively calculate the height of the tree to the left of the root.
2. Recursively calculate the height of the tree to the right of the root.
3. Pick the larger height from the two answers and add one to it (to account for the root node).

## Code

#include <iostream>
using namespace std;

struct Node {
int value;
Node *left, *right;

Node(int val)
{
this->value = val;
this->left = this->right = NULL;
}
};

int maxDepth(Node * root)
{
// Root being null means tree doesn't exist.
if (root == NULL)
return 0;

// Get the depth of the left and right subtree
// using recursion.
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);

// Choose the larger one and add the root to it.
if (leftDepth > rightDepth)
return leftDepth + 1;
else
return rightDepth + 1;
}

// driver code
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->right->right->left = new Node(8);
root->right->left->right = new Node(7);
cout << "The maximum depth is: " << maxDepth(root) << endl;
}

RELATED TAGS

maximum depth
binary tree
recursion 