Height of Binary Tree

Problem Statement

Given a binary tree, write a function to find its height. The height of a binary tree is defined as the number of edges along the longest path from the root node to a leaf node. An empty tree has a height of -1.

Examples

Example 1:

Input:

       1
      / \
     2   3
    / \
   4   5

Output: 2

Explanation: Longest path from root (node 1) to a leaf is through
nodes 1 -> 2 -> 4 or 1 -> 2 -> 5, which has 2 edges.

Example 2:

Input:

       1
      / \
     2   3
    /     \
   4       5
  /
 6

Output: 3

Explanation: Longest path from root to a leaf is through node 1 -> 2
-> 4 -> 6, which has 3 edges.

Example 3:

Input:
1

Output: 0

Explanation: The tree only contains the root node, so its height is 0.

Dry Run:

    1
   / \
  2   3
 / \
4   5

Expected Output:

The height of this tree should be 2.

Start at the root (node 1):

• height(root) is called with root being 1.
• Since root is not nullptr, we proceed to find the height of the left and right subtrees.

Calculate the height of the left subtree of node 1 (node 2):

• height(root->left) is called with root->left being 2.
• Since root->left is not nullptr, we proceed to find the height of the left and right subtrees of node 2.

Calculate the height of the left subtree of node 2 (node 4):

• height(root->left->left) is called with root->left->left being 4.
• Since root->left->left is not nullptr, we proceed to find the height of its left and right subtrees.

Calculate the height of the left subtree of node 4 (nullptr):

• height(root->left->left->left) is called with root->left->left->left being nullptr.
• Since root->left->left->left is nullptr, we return -1.

Calculate the height of the right subtree of node 4 (nullptr):

• height(root->left->left->right) is called with root->left->left->right being nullptr.
• Since root->left->left->right is nullptr, we return -1.

Calculate height of node 4:

• We now have the heights of the left and right subtrees of node 4, which are both -1.
• The height of node 4 is 1 + max(-1, -1) = 0.
• We return 0 to the previous recursive call for node 2.

Calculate the height of the right subtree of node 2 (node 5):

• height(root->left->right) is called with root->left->right being 5.
• Since root->left->right is not nullptr, we proceed to find the height of its left and right subtrees.

Calculate the height of the left subtree of node 5 (nullptr):

• height(root->left->right->left) is called with root->left->right->left being nullptr.
• Since root->left->right->left is nullptr, we return -1.

Calculate the height of the right subtree of node 5 (nullptr):

• height(root->left->right->right) is called with root->left->right->right being nullptr.
• Since root->left->right->right is nullptr, we return -1.

Calculate height of node 5:

• We now have the heights of the left and right subtrees of node 5, which are both -1.
• The height of node 5 is 1 + max(-1, -1) = 0.
• We return 0 to the previous recursive call for node 2.

Calculate height of node 2:

• We now have the heights of the left and right subtrees of node 2: the left subtree (node 4) has height 0, and the right subtree (node 5) has height 0.
• The height of node 2 is 1 + max(0, 0) = 1.
• We return 1 to the previous recursive call for the root node 1.

Calculate the height of the right subtree of node 1 (node 3):

• height(root->right) is called with root->right being 3.
• Since root->right is not nullptr, we proceed to find the height of its left and right subtrees.

Calculate the height of the left subtree of node 3 (nullptr):

• height(root->right->left) is called with root->right->left being nullptr.
• Since root->right->left is nullptr, we return -1.

Calculate the height of the right subtree of node 3 (nullptr):

• height(root->right->right) is called with root->right->right being nullptr.
• Since root->right->right is nullptr, we return -1.

Calculate height of node 3:

• We now have the heights of the left and right subtrees of node 3, which are both -1.
• The height of node 3 is 1 + max(-1, -1) = 0.
• We return 0 to the previous recursive call for the root node 1.

Calculate height of root node 1:

• We now have the heights of the left and right subtrees of the root node 1: the left subtree (node 2) has height 1, and the right subtree (node 3) has height 0.
• The height of the root node 1 is 1 + max(1, 0) = 2.

height(Node 1)
  ├── height(Node 2)
  │      ├── height(Node 4) -> returns 0
  │      └── height(Node 5) -> returns 0
  │      => height(Node 2) = 1 + max(0, 0) = 1
  └── height(Node 3) -> returns 0
  => height(Node 1) = 1 + max(1, 0) = 2

Code:

#include <iostream>
#include <algorithm>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Function to calculate the height of a binary tree
int height(TreeNode* root) {
    // Base condition: if the tree is empty, return -1
    if (root == nullptr) {
        return -1;
    }
    // Recursive call for left and right subtree heights
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    // Calculate the height by taking the maximum of left and right heights, and add 1
    return 1 + max(leftHeight, rightHeight);
}

// Test the function
int main() {
    // Constructing a binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Calculate and print the height of the binary tree
    cout << "Height of the tree: " << height(root) << endl;

    return 0;
}

Explanation:

1. Base Condition: If root is nullptr, return -1, meaning an empty tree has a height of -1.
2. Recursive Calls: Recursively call height on root->left and root->right to get the heights of the left and right subtrees.
3. Induction Step: Compute the height of the current node by taking 1 + max(leftHeight, rightHeight). This adds one edge for the current node’s height.

Complexity Analysis:

• Time Complexity: O(n)
  • Since we are visiting every node in the tree exactly once.
• Space Complexity: O(n)
  • This is determined by the call stack used in recursion, which depends on the height of the tree.
  • Balanced tree: If the tree is balanced, space complexity of O(log n) for the recursive call stack.
  • Skewed Tree: If the tree is skewed (either left or right), leading to a worst-case space complexity of O(n) for the call stack.