Determine the Height of Binary Trees

Question: given a root of a binary tree, write an algorithm to find the tree's height.

Solution: the height of a binary tree is the length of the path from the root to the deepest leaf node of the tree. For example, the following tree has height of 3:

To find the height, we need to count the number of nodes on the path from root to the deepest leaf. This can be done recursively. Here is the code in C++:

//basic tree node definition
struct Node
{
  int data;
  struct Node* left;
  struct Node* right;
};

int getBinaryTreeHeight(struct Node* root)
{
   if (root == NULL)
      return 0;

   int leftHeight = getBinaryTreeHeight(root->left);
   int rightHeight = getBinaryTreeHeight(root->right);

   return 1 + (leftHeight <= rightHeight ? rightHeight : leftHeight);
}

Explanation: assuming that we have a tree node structure just like that in the example code, our method takes in a pointer to the root and return the height of that root's tree. Recursively, a tree's height is the height of its subtrees. So if we know the height of the subtrees, we know the height of the tree. For each node under the current root, we do the following:

1. If the current node is null, we simply return 0 because a rooted tree with no root has height 0.
2. Next we find the height of the left subtree and the right subtree.
3. Lastly, either left or right subtree's height plus one is returned as the height of the current root's tree. Why do we add one into the return result? Well because the current node is counted as one height unit if it is not null.

By the end of the recursive calls, the returned sum is the height of the tree whose root is the argument to the function.

That's the end of this post. Thanks for reading :)