C++ Program to Find the Height of a Binary Tree

1. Introduction

Finding the height (or depth) of a binary tree is a fundamental problem in computer science, frequently encountered in interviews and academic settings. The height of a binary tree is the longest path from the root node to any leaf. 

In this post, we will walk you through the code to calculate the height of a binary tree using a C++ program.

2. Program Overview

We will use a simple recursive approach to determine the height of the tree. 

Here's a brief overview:

- Node class: This represents each node in our binary tree.

- BinaryTree class: This contains the core functions such as insert for populating the tree and findHeight for determining its height.

- The findHeight function will work by traversing the tree recursively, counting the number of levels until reaching the leaves.

3. Code Program

#include<iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class BinaryTree {
private:
    Node* root;

    int findHeight(Node* node) {
        if (!node) return 0;

        int leftHeight = findHeight(node->left);
        int rightHeight = findHeight(node->right);

        return max(leftHeight, rightHeight) + 1;
    }

public:
    BinaryTree() : root(nullptr) {}

    void insert(int val) {
        // Insert function logic here for simplicity
        // This can be any preferred insertion method, e.g., level order
    }

    int getHeight() {
        return findHeight(root);
    }
};

int main() {
    BinaryTree tree;
    // Insert elements into the tree for demonstration
    // For example: tree.insert(5), tree.insert(3), tree.insert(8) and so on

    cout << "Height of the tree: " << tree.getHeight() << endl;

    return 0;
}

Output:

Considering a tree structure with root 5, left child 3, and right child 8, the output will be:
Height of the tree: 1
(Note: This output assumes only one level below the root. The height will change depending on the structure and depth of the tree you create.)

4. Step By Step Explanation

1. The core of our program lies in the findHeight function. When this function is called with a node, it tries to compute the height of the tree by considering both the left and right subtrees. 

2. For any node, the height will be the maximum height between its left and right subtrees plus one (for the current level). If a node is null, it returns 0. This recursive approach ensures that every node and level in the tree is considered.

2. In the main function, after populating the tree with some nodes, we simply call the getHeight function to retrieve and display the tree's height.