Trusted answers to developer questions

Finding the maximum depth of a binary tree

Get Started With Machine Learning

Learn the fundamentals of Machine Learning with this free course. Future-proof your career by adding ML skills to your toolkit — or prepare to land a job in AI or Data Science.

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:

svg viewer

The maximum depth, or height, of this tree is 44; node 77 and node 88 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
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?