2.3) Find Height of Binary Tree

Given a Binary Tree, write a function to find and return the height of the binary tree.

The height of a Binary Tree is the maximum number of edges on the longest path from the root node to any leaf node.

Consider the following Binary Tree:

        5
      /   \
     3     8
    / \   / \
   2   4 6   10

Expected Output:

The height of the Binary Tree is 3.

The height of a Binary Tree is a fundamental concept that measures the length of the longest path from the root node to any leaf node in the tree. It represents the depth of the tree, indicating how many levels of nodes exist from the root to the deepest leaf. The height is counted in terms of the number of edges along the path, not the number of nodes.

How to Calculate Height:

The height of a Binary Tree can be calculated using a recursive approach. Here’s how you can calculate it:

1. If the tree is empty (root is nullptr), the height is -1.
2. If the tree is not empty:
   • Recursively calculate the height of the left subtree.
   • Recursively calculate the height of the right subtree.
   • The height of the current node’s subtree is the maximum of the heights of its left and right subtrees, plus 1 (for the current node itself).

This approach ensures that you explore all paths from the root to the leaf nodes, calculating the height for each subtree along the way.

Time and Space Complexity:

The time complexity of finding the height of a Binary Tree is O(n), where n is the number of nodes in the tree. This is because we need to visit every node once. The space complexity is O(h), where h is the height of the tree, due to the space used by the recursive function call stack.

C++ Solution:

#include <iostream>
#include <algorithm> // Include the algorithm library for max function

// Define a node structure for the Binary Tree
struct Node {
    int data;
    Node* left;
    Node* right;

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

// Function to find the height of Binary Tree
int findHeight(Node* root) {
    if (root == nullptr)
        return -1; // Height of an empty tree is -1

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

    // Return the maximum of heights of left and right subtrees, plus 1 for the current node
    return std::max(leftHeight, rightHeight) + 1;
}

int main() {
    // Creating the Binary Tree
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(8);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->left = new Node(6);
    root->right->right = new Node(10);

    // Find and print the height of the Binary Tree
    int height = findHeight(root);
    std::cout << "Height of Binary Tree: " << height << std::endl;

    return 0;
}

Code Explanation:

• We define a Node structure for the Binary Tree, holding data, a left child, and a right child.
• The findHeight function recursively finds the height of the Binary Tree. For each node, it compares the heights of its left and right subtrees using the std::max function from the algorithm library and adds 1 for the current node.
• In the main function, we create the Binary Tree and call findHeight to calculate and print the height of the tree.

When you run the code, it calculates and prints the height of the given Binary Tree, which is 3 in this case.

Output:

Height of Binary Tree: 3

Why Measure Height:

1. Performance Analysis: The height of a Binary Tree is essential for analyzing the performance of tree-based algorithms. A balanced tree (with smaller height) usually leads to more efficient operations like searching, insertion, and deletion.
2. Memory Management: The height can help determine the memory requirements for various tree operations. It can guide decisions on how to allocate resources and nodes.
3. Problem Solving: In many coding problems involving Binary Trees, understanding and utilizing the height is crucial for devising efficient algorithms and solutions.
4. Optimization: Knowledge of the height can guide you in optimizing the traversal and searching strategies within the tree.