Monday, 17 July 2017 03:52

## Write a Program to Find the Maximum Depth or Height of a Tree

Written by
Rate this item

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