The maximum depth or height of a binary is the number of nodes from root node to its farthest or deepest leaf node. For example the below binary tree has height or depth is 3.

C program to calculate maximum depth or height of a binary tree

Recursive solution

#include 
#include 

typedef struct Node
{
  struct Node *left;		/* left child */
  char data;			/* data to be stored */
  struct Node *right;		/* right child */
} Node;

Node *createNode ();
int treeHeight (Node * node);

int
main ()
{

  Node *A = createNode ();
  A->data = 'A';
  Node *B = createNode ();
  B->data = 'B';
  Node *C = createNode ();
  C->data = 'C';
  Node *D = createNode ();
  D->data = 'D';
  Node *E = createNode ();
  E->data = 'E';
  Node *F = createNode ();
  F->data = 'F';
// create tree as shown in above figure

  A->left = B;
  A->right = C;
  B->left = D;
  B->right = F;
  C->right = E;
  C->left = NULL;

/* calculate height*/
  printf ("The height of tree is %d\n", treeHeight (A));
  return 0;
}

Node *
createNode ()
{
  Node *tmp = (Node *) malloc (sizeof (Node));
  tmp->left = NULL;
  tmp->right = NULL;
  return tmp;
}

int
treeHeight (Node * node)
{
  int leftHeight = 0;
  int rightHeight = 0;
/* empty tree is defined as height of -1 */
  if (node == NULL)
    return 0;
  else if (node != NULL)
    {
      leftHeight = treeHeight (node->left);
      rightHeight = treeHeight (node->right);
      if (leftHeight > rightHeight)
	return (leftHeight + 1);
      else
	return (rightHeight + 1);
    }
}


Related Contents to follow