#### Tree

Problem
Implement an algorithm to find the height of a Binary Tree.

Solution
Height of the tree is defined as the number of nodes along the path from root node to the deepest leaf node.
The height of the tree shown below is 4. The paths with maximum number of nodes are { 29 , 24 , 16 , 31 } and
{ 19 , 24 , 16 , 31 }
.

We use a recursive approach to find the maximum of left subtree height and right subtree height and add 1 for the parent node. This process continues till we reach the deepest leaf node. See the implementation below.

#include<iostream>
using namespace std;

// get the max of two no.s
int max(int a, int b) {
return ((a > b) ? a : b);
}

typedef struct node {
int value;
struct node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
node *new_node = new node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

// compute height of the tree
int getHeight(node *root) {
if (root == NULL)
return 0;

// find the height of each subtree
int lh = getHeight(root->left);
int rh = getHeight(root->right);

return 1 + max(lh,rh);
}

// create the tree
node *createTree() {
node *root = getNewNode(31);
root->left = getNewNode(16);
root->right = getNewNode(52);
root->left->left = getNewNode(7);
root->left->right = getNewNode(24);
root->left->right->left = getNewNode(19);
root->left->right->right = getNewNode(29);
return root;
}

// main
int main() {
node *root = createTree();
cout<<"\nHeight of the tree is "<<getHeight(root);
cout<<endl;
return 0;
}