Trusted answers to developer questions
Finding the maximum depth of a binary tree
Educative Answers TeamThe 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 ; node and node are both four nodes away from the root.
Algorithm
The algorithm uses recursion to calculate the maximum height:
- Recursively calculate the height of the tree to the left of the root.
- Recursively calculate the height of the tree to the right of the root.
- 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 ©2022 Educative, Inc. All rights reserved
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
