Introduction

The height of a binary tree is defined as the number of edges on the longest path from the root node to a leaf node. In other words, it is the depth of the tree. The height of an empty tree is defined to be -1, and the height of a single-node tree is 0.

In this guide, we will implement a C++ program that recursively calculates the height of a binary tree by traversing the tree and computing the maximum depth of the left and right subtrees.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure to represent the nodes in the binary tree.
2. Write a recursive function findHeight that computes the height of the tree.
3. Implement the main function to test the algorithm with a sample binary tree.

Code Implementation

// C++ program to find the height of a binary tree

#include <iostream>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to find the height of a binary tree
int findHeight(TreeNode* root) {
    // Base case: if the tree is empty, return -1
    if (root == NULL) {
        return -1;
    }

    // Recursively find the height of the left and right subtrees
    int leftHeight = findHeight(root->left);
    int rightHeight = findHeight(root->right);

    // Return the maximum height of the two subtrees plus 1
    return 1 + max(leftHeight, rightHeight);
}

// Helper function to insert a new node into the binary tree (for testing purposes)
TreeNode* insert(TreeNode* node, int val) {
    if (node == NULL) return new TreeNode(val);  // If the tree is empty, create a new node

    // Otherwise, recursively insert the value into the left or right subtree
    if (val < node->val)
        node->left = insert(node->left, val);
    else
        node->right = insert(node->right, val);

    return node;
}

// Helper function to perform in-order traversal of the binary tree (for testing purposes)
void inOrderTraversal(TreeNode* root) {
    if (!root) return;

    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

int main() {
    /* Sample Binary Tree:
              10
            /    \
           5      15
          / \    /  \
         3   7  12   20
    */

    // Create an empty binary tree
    TreeNode* root = NULL;

    // Insert nodes into the binary tree
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 12);
    root = insert(root, 20);

    // Find the height of the binary tree
    int height = findHeight(root);
    cout << "The height of the binary tree is: " << height << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary tree. Each node stores a value val and pointers to its left and right children.
2. findHeight function: This is a recursive function that calculates the height of the tree:
   • If the node is NULL (i.e., the tree is empty), the height is -1 (base case).
   • The function recursively calculates the height of the left and right subtrees.
   • The height of the current node is the maximum height of its left and right subtrees plus 1.
3. insert function: This helper function is used to insert nodes into the binary tree. It adds a new node at the correct position based on its value relative to the current node.
4. inOrderTraversal function: This function performs an in-order traversal (left subtree, root, right subtree) of the binary tree and prints the nodes. It is optional and used for testing purposes.

How the Algorithm Works

The algorithm works by recursively calculating the height of the left and right subtrees of each node. For each node:

• If the node is NULL (base case), the height is -1.
• Otherwise, the height of the node is the maximum height of the left and right subtrees, plus 1 to account for the current node.

The function returns the height of the entire tree when called on the root node.

Sample Output

If you run the above program with the provided sample binary tree, the output will be:

The height of the binary tree is: 2

In this example, the height of the tree is 2, as the longest path from the root to a leaf node consists of two edges (10 → 15 → 20).

Conclusion

In this program, we implemented a recursive algorithm to find the height of a binary tree in C++. The height is calculated as the number of edges on the longest path from the root to a leaf node. The algorithm visits each node exactly once, making the time complexity O(N), where N is the number of nodes in the tree. The space complexity is O(H), where H is the height of the tree, due to the recursive call stack.