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;
}

class Node: 
  def __init__(self , val): 
      self.value = val  
      self.left = None
      self.right = None

def maxDepth(root):
  # Null node has 0 depth.
  if root == None:
    return 0

  # Get the depth of the left and right subtree 
  # using recursion.
  leftDepth = maxDepth(root.left)
  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
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
root.right.right = Node(6)
root.right.right.left = Node(8)
root.right.left.right = Node(7)
print("The max depth is:", maxDepth(root))

Python

class Node  
{ 
  int value; 
  Node left, right; 
   
  Node(int val)  
  { 
    value = val; 
    left = right = null; 
  } 
}

class BinaryTree  
{ 
  Node root;
  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
  public static void main(String[] args)  
  { 
    BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(1);
    tree.root.left = new Node(2);
    tree.root.right = new Node(3);
    tree.root.left.left = new Node(4);
    tree.root.right.left = new Node(5);
    tree.root.right.right = new Node(6);
    tree.root.right.right.left = new Node(8);
    tree.root.right.left.right = new Node(7);
    System.out.println("Max depth: " + tree.maxDepth(tree.root));              
  } 
} 

Java

using System; 

public class Node 
{ 
	public int value; 
	public Node left, right; 

	public Node(int val) 
	{ 
		value = val; 
		left = right = null; 
	} 
} 

public class BinaryTree 
{ 
	Node root; 

	int maxDepth(Node root) 
	{ 
		if (root == null) 
			return 0; 

    // Recursively find the depth of each subtree.
    int leftDepth = maxDepth(root.left); 
    int rightDepth = maxDepth(root.right); 

    // Get the larger depth and add 1 to it to
    // account for the root.
    if (leftDepth > rightDepth) 
      return (leftDepth + 1); 
    else
      return (rightDepth + 1); 
	} 
	
	// Driver code
	public static void Main() 
	{ 
		BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(1);
    tree.root.left = new Node(2);
    tree.root.right = new Node(3);
    tree.root.left.left = new Node(4);
    tree.root.right.left = new Node(5);
    tree.root.right.right = new Node(6);
    tree.root.right.right.left = new Node(8);
    tree.root.right.left.right = new Node(7);
		Console.WriteLine("Max depth: " + tree.maxDepth(tree.root)); 
	} 
} 

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: 