How to Find Height of Binary Tree in C: Simple Guide

To find the height of a binary tree in C, use a recursive function that returns 0 for a NULL node and otherwise returns 1 plus the maximum height of its left and right subtrees. This function measures the longest path from the root node down to the farthest leaf node.

Syntax

The function to find the height of a binary tree typically looks like this:

• struct Node*: Pointer to the current node.
• Returns an int representing the height.
• Uses recursion to explore left and right children.
• Returns 0 if the node is NULL, meaning no tree exists.

c

int height(struct Node* node) {
    if (node == NULL) {
        return 0;
    } else {
        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
    }
}

Example

This example creates a simple binary tree and calculates its height using the recursive function.

c

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Function to find height of binary tree
int height(struct Node* node) {
    if (node == NULL) {
        return 0;
    } else {
        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
    }
}

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

    printf("Height of the binary tree is %d\n", height(root));
    return 0;
}

Output

Height of the binary tree is 3

Common Pitfalls

Common mistakes when finding the height of a binary tree include:

• Not handling the NULL node case, which causes crashes.
• Confusing height with the number of nodes; height counts edges or levels, not nodes.
• Forgetting to add 1 after comparing left and right subtree heights.

Always return 0 for NULL nodes and add 1 to the maximum subtree height.

c

/* Wrong way: Missing NULL check and no +1 */
int wrongHeight(struct Node* node) {
    int leftHeight = wrongHeight(node->left); // crashes if node is NULL
    int rightHeight = wrongHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight); // no +1
}

/* Correct way: */
int correctHeight(struct Node* node) {
    if (node == NULL) {
        return 0;
    }
    int leftHeight = correctHeight(node->left);
    int rightHeight = correctHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

Quick Reference

Height of Binary Tree Cheat Sheet:

• height(NULL) = 0 (empty tree)
• Height = 1 + max(height(left subtree), height(right subtree))
• Use recursion to explore all nodes
• Base case is NULL node

Key Takeaways

Use a recursive function that returns 0 for NULL nodes to find binary tree height.

Height is 1 plus the maximum height of left and right subtrees.

Always check for NULL nodes to avoid crashes.

Height counts levels, not the number of nodes.

Adding 1 after comparing subtree heights is essential.