The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

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.sint 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 treeint getHeight(node *root) {
if (root == NULL)
return 0;
// find the height of each subtreeint 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;
}
// mainint main() {
node *root = createTree();
cout<<"\nHeight of the tree is "<<getHeight(root);
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
// get the max of two no.sint 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 treeint getHeight(node *root) {
if (root == NULL)
return 0;
// find the height of each subtreeint 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;
}
// mainint main() {
node *root = createTree();
cout<<"\nHeight of the tree is "<<getHeight(root);
cout<<endl;
return 0;
}