Write a recursive C function to calculate the height of a binary tree

by

int countHeight(struct node* t)
{
int l,r;
if(!t)
return 0;
if((!(t->left)) && (!(t->right)))
return 0;
l=countHeight(t->left);
r=countHeight(t->right);
return (1+((l>r)?l:r));
}

Sure, here’s a recursive C function to calculate the height of a binary tree:

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

// Definition of a binary tree node
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 calculate the height of a binary tree
int height(struct Node* root) {
// Base case: if the tree is empty, height is 0
if (root == NULL)
return 0;
else {
// Compute the height of the left and right subtrees recursively
int leftHeight = height(root->left);
int rightHeight = height(root->right);

// Return the maximum of the left and right subtree heights, plus 1 for the root
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
}

// Main function to test the above functions
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)); // Output should be 3

return 0;
}

Explanation:

  • The height() function calculates the height of the binary tree recursively.
  • It checks if the tree is empty. If so, it returns 0.
  • If the tree is not empty, it recursively calculates the height of the left and right subtrees.
  • It returns the maximum of the heights of the left and right subtrees, plus 1 for the current root.
  • The main() function creates a binary tree and tests the height() function by passing the root node.