How to find a height of a binary tree and counting the leaf nodes in C?

               Binary tree is a tree which has two nodes. It has a root node. It has a left sub tree and right sub tree.

Let us implement the c program to count the leaf nodes and height of a binary tree.

C implementation:

              This implementation starts by including header files.

• Next, declare the node structure for tree. It has node with data, left and right values.
• Now, a new node is created by allocating its memory.
• The values are initialised.  
• To calculate the heights of the tree, traverse the tree.
• To count the leaf nodes, check the root nodes, traverse each sub tree separately and count the nodes.
• In the main() function, create the root node and all child nodes by using the newNode() function.
• Call the height() function and countLeafNodes() function to display the output.

C Code:

#include <stdio.h>

#include <stdlib.h>

// Declaration of structure for tree node

struct t_Node {

    int t_data;

    struct t_Node *t_left, *t_right;

};

// creation of a new node

struct t_Node* newNode(int data) {

    struct t_Node* node = (struct t_Node*)malloc(sizeof(struct t_Node));

    node->t_data = data;

    node->t_left = node->t_right = NULL;

    return node;

}

// Calculation of  height of tree

int height(struct t_Node* root) {

    if (root == NULL)

        return 0;

    int leftHeight = height(root->t_left);

    int rightHeight = height(root->t_right);

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

}

// let us count the leaf nodes

int countLeafNodes(struct t_Node* root) {

    if (root == NULL)

        return 0;

    if (root->t_left == NULL && root->t_right == NULL)

        return 1;

    return countLeafNodes(root->t_left) + countLeafNodes(root->t_right);

}

int main() {

    // sample tree

    struct t_Node* root = newNode(1);

    root->t_left = newNode(2);

    root->t_right = newNode(3);

    root->t_left->t_left = newNode(4);

    root->t_left->t_right = newNode(5);

    root->t_right->t_left = newNode(6);

    root->t_right->t_right = newNode(7);

    root->t_left->t_left->t_left = newNode(8);

    root->t_left->t_left->t_right = newNode(9);

    printf("Height of tree: %d\n", height(root));

    printf("Leaf nodes count: %d\n", countLeafNodes(root));

    return 0;

}

Output:

Height of tree: 4

Leaf nodes count: 5

Hope, this code is useful to you. Thus ,the C Program to find the height and counting the leaf nodes was implemented successfully.