top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Count Number of Leaf Nodes in a Binary Tree

+1 vote
723 views

Its a recursive function . We have to traverse the whole tree and at each node we will check if a node is without child then will increase the count.

Binary Tree

Number of leaf node in the above tree - 3

Sample Code

struct node
{
    int data;
    struct node *lsubtree;
    struct node *rsubtree;
};

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->lsubtree = null;
    new->rsubtree = null;
    new->data = data;

    return new;
} 

void add_node(int data, struct node **head)
{
    if (*head == null)
    {
        *head = create_node(data);
    }
    else if (data < (*head)->data)
    {
        add_node(data, &(*head)->lsubtree);
    }
    else if (data > (*head)->data)
    {
        add_node(data, &(*head)->rsubtree);
    }
}

struct node *search(int data, struct node *head)
{
    if (head != null)
    {
        if (data == head->data)
        {
            return head;
        }
        else if (data < head->data)
        {
            return search(data, head->lsubtree);
        }
        else
        {
            return search(data, head->rsubtree);
        }
    }
    else return null;
}

void preorder_traversal (struct node * root)
{
    if (root != NULL) {
        printf("%c ", root->data);
        preorder_traversal(root->lsubtree);
        preorder_traversal(root->rsubtree);
    }
}

void inorder_traversal (struct node * root)
{
    if (root != NULL) {
        inorder_traversal(root->lsubtree);
        printf("%c ", root->data);
        inorder_traversal(root->rsubtree);
    }
}

void postorder_traversal (struct node * root)
{
    if (root != NULL) {
        postorder_traversal(root->lsubtree);
        postorder_traversal(root->rsubtree);
        printf("%c ", root->data);
    }
}

void count_leaf_node(struct node * root, int *count)
{
    if (root == NULL)
    {
        return;
    }
    if (root->lsubtree == NULL && root->rsubtree == NULL)
    {
        *count = *count + 1;
    }
    count_leaf_node(root->lsubtree, count);
    count_leaf_node(root->rsubtree, count);
}
posted Sep 24, 2014 by Sandeep Otari

  Promote This Article
Facebook Share Button Twitter Share Button LinkedIn Share Button

...