# Write a function to find the depth of a binary tree? Please give sample code?

110 views
Write a function to find the depth of a binary tree? Please give sample code?
posted Nov 23, 2015

Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. See below pseudo code and program for details.

Algorithm:

``````maxDepth()
1. If tree is empty then return 0
2. Else
(a) Get the max depth of left subtree recursively  i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively  i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depth
``````

See the below diagram for more clarity about execution of the recursive function maxDepth() for above example tree.

`````` maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1
= 2 + 1
/    \
/         \
/             \
/                 \
/                     \
maxDepth('1')                  maxDepth('3') = 1

= max(maxDepth('4'), maxDepth('5')) + 1
= 1 + 1   = 2
/    \
/        \
/            \
/                \
/                    \
maxDepth('4') = 1     maxDepth('5') = 1
``````

Implementation:

``````#include<stdio.h>
#include<stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Compute the "maxDepth" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
struct node *root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Hight of tree is %d", maxDepth(root));

getchar();
return 0;
}
``````

Program to find depth of Binary Tree

``````#include<stdio.h>
#include<stdlib.h>

/* A binary tree node has data, pointer to left child and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Compute the "maxDepth" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*) malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
struct node *root = newNode(1);

root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Hight of tree is %d", maxDepth(root));

getchar();
return 0;
}
``````