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 ; node and node are both four nodes away from the root.
The algorithm uses recursion to calculate the maximum height:
#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;elsereturn rightDepth + 1;}// driver codeint 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;}