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

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. The height of a binary tree is the length of the longest path from the root node to a leaf node. Understanding the height of a binary tree is important for various applications, such as balancing the tree, optimizing search operations, and more. This article will guide you through the implementation of a C++ program to find the height of a binary tree, providing detailed explanations and examples to enhance your understanding.

Prerequisites

Before diving into the implementation, it’s important to understand the following concepts:

• Binary Tree: A tree data structure in which each node has at most two children.
• Height of a Tree: The length of the longest path from the root node to a leaf node.
• Tree Traversal: The process of visiting all nodes in a tree in a specific order (e.g., in-order, pre-order, post-order).
• Recursion: A method where the solution to a problem depends on solutions to smaller instances of the same problem.

Familiarity with C++ programming, including classes and recursion, will be beneficial.

Implementing the Binary Tree

To find the height of a binary tree, we will:

1. Define a class for the binary tree node.
2. Implement a function to calculate the height recursively.
3. Create a binary tree and use the function to find its height.

Pseudocode for Finding Height

1. If the current node is null, return 0.
2. Recursively find the height of the left subtree.
3. Recursively find the height of the right subtree.
4. Return the greater of the heights of the left and right subtrees, plus 1.

Example

Example 1: Simple Binary Tree

Binary Tree Representation

Consider a simple binary tree:

      1
     / \
    2   3
   / \
  4   5

In this tree, the height is 3.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int findHeight(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftHeight = findHeight(root->left);
    int rightHeight = findHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "Height of the tree: " << findHeight(root) << endl;

    return 0;
}

Output

Height of the tree: 3

Additional Examples

Example 2: Larger Binary Tree

Binary Tree Representation

Consider a larger binary tree:

         1
       /   \
      2     3
     / \     \
    4   5     6
       / \
      7   8

In this tree, the height is 4.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int findHeight(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftHeight = findHeight(root->left);
    int rightHeight = findHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->right->left = new Node(7);
    root->left->right->right = new Node(8);

    cout << "Height of the tree: " << findHeight(root) << endl;

    return 0;
}

Output

Height of the tree: 4

Example 3: Binary Tree with Single Node

Binary Tree Representation

Consider a binary tree with a single node:

  1

In this tree, the height is 1.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int findHeight(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftHeight = findHeight(root->left);
    int rightHeight = findHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

int main() {
    Node* root = new Node(1);

    cout << "Height of the tree: " << findHeight(root) << endl;

    return 0;
}

Output

Height of the tree: 1

Conclusion

Finding the height of a binary tree is a common problem that can be efficiently solved using a recursive approach. By understanding the structure of a binary tree and implementing the height calculation function, you can easily determine the height of the tree