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

*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.*

*Recursive solution*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <stdio.h> #include <stdlib.h> 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); } } |

## Leave a Reply