The height of a binary tree is a fundamental property representing the maximum depth from the root to a leaf node. While recursion is the most common approach to calculate height, an iterative approach using a queue can achieve the same result. Having both methods allows programmers to choose based on their requirements or memory constraints.
Understanding the Problem
The height of a binary tree is the number of edges on the longest path from the root to a leaf. The recursive approach computes this by comparing the heights of left and right subtrees. The iterative approach processes the tree level by level, counting how many levels exist, which directly corresponds to the tree’s height. Using a queue for level order traversal makes this straightforward.
Program 1: Recursive Approach
This program demonstrates how to find the height of a binary tree using recursion. It computes the height of the left and right subtrees and returns the greater value plus one for the current node.
#include <stdio.h>
#include <stdlib.h>
// Structure for a tree node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Function to create a new node
Node* createNode(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Recursive function to calculate height
int findHeightRecursive(Node *root) {
if (root == NULL)
return 0;
int leftHeight = findHeightRecursive(root->left);
int rightHeight = findHeightRecursive(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
int main() {
Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Height (Recursive): %d\n", findHeightRecursive(root));
return 0;
}The recursive method ensures every node is visited, comparing left and right subtree heights, and adding one for the current root. This is simple and elegant but may use extra memory on the call stack for large trees.
Program 2: Iterative Approach (Using Queue)
This program uses level order traversal with a queue to calculate the height iteratively. Each level processed increments a counter representing the tree’s height.
#include <stdio.h>
#include <stdlib.h>
// Node structure
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Queue structure
typedef struct Queue {
Node **arr;
int front, rear, size, capacity;
} Queue;
// Create a new node
Node* createNode(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Create a queue
Queue* createQueue(int capacity) {
Queue *queue = (Queue*)malloc(sizeof(Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->arr = (Node**)malloc(capacity * sizeof(Node*));
return queue;
}
// Check if queue is empty
int isQueueEmpty(Queue *queue) {
return (queue->size == 0);
}
// Enqueue
void enqueue(Queue *queue, Node *item) {
if (queue->size == queue->capacity) return; // Overflow
queue->rear = (queue->rear + 1) % queue->capacity;
queue->arr[queue->rear] = item;
queue->size++;
}
// Dequeue
Node* dequeue(Queue *queue) {
if (isQueueEmpty(queue)) return NULL;
Node *item = queue->arr[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size--;
return item;
}
// Iterative function to find height
int findHeightIterative(Node *root) {
if (!root) return 0;
Queue *queue = createQueue(100);
enqueue(queue, root);
int height = 0;
while (!isQueueEmpty(queue)) {
int levelSize = queue->size;
height++;
for (int i = 0; i < levelSize; i++) {
Node *current = dequeue(queue);
if (current->left) enqueue(queue, current->left);
if (current->right) enqueue(queue, current->right);
}
}
free(queue->arr);
free(queue);
return height;
}
int main() {
Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Height (Iterative): %d\n", findHeightIterative(root));
return 0;
}The iterative method avoids recursion by counting levels. Each pass through the queue represents one level of the tree, incrementing the height counter accordingly. This is especially useful for very deep trees where recursion might cause stack overflow.
FAQs
Q1: Which method is better, recursive or iterative?
Recursive is simpler and elegant, but iterative is safer for very deep trees to avoid stack overflow.
Q2: What is the time complexity for both approaches?
Both methods have O(n) time complexity, as each node is visited once.
Q3: Can we calculate height without recursion or queue?
Yes, using depth-first traversal with a stack is also possible, but it requires careful tracking of depth.
Q4: What is the height of an empty tree?
0. A tree with a single node has a height of 1.
Conclusion
Finding the height of a binary tree is essential for understanding its structure and is used in many algorithms like balancing. The recursive approach is concise, while the iterative approach using a queue is safe for large trees. Mastering both gives flexibility depending on the situation.
References & Additional Resources
A curated selection of books and online tutorials for learning binary tree height calculation, traversal methods, and tree properties in C.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Covers binary trees, height calculation, traversal techniques, and memory management in C.
- Programiz: Binary Tree Traversals – Beginner-friendly guide on binary tree traversals, including in-order, pre-order, and post-order methods.
- GeeksforGeeks: Height of a Binary Tree – Step-by-step explanation and C code for computing the maximum depth of a tree.
- Tutorialspoint: Tree Properties and Operations – Overview of tree concepts, operations, and properties with C examples.
