a shot of dev knowledge

RELATED TAGS

Finding the maximum depth of a binary tree

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

RELATED COURSES

View all Courses

Keep Exploring