Home Trees Give an algorithm to find the number of full nodes in a binary tree.

Give an algorithm to find the number of full nodes in a binary tree.

by nikoo28
0 comment

Question: Given the root pointer to a binary tree, find the number of full nodes.

Input: Sample Tree (Pointer to node 1 is given). Find the number of full nodes.
sample_treeOutput: Number of full nodes = 3

According to the definition, the set of all nodes with both left and right child are called as full nodes.

In the above example, we have the nodes – 1. 2, 3 as full nodes.

We can perform a level order traversal and count the number of nodes, who have their right child and left child as not null. Return the count in the end.

#include<stdio.h>
#include<malloc.h>

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

int numberOfFullNodes(struct binaryTreeNode * root)
{
	// Level order traversal
	struct binaryTreeNode * temp = NULL;
	struct queue * Q = NULL;

	// Maintain a count
	int count = 0;

	if(root == NULL)
		return 0;

	Q = enQueue(Q, root);
	while(!isQueueEmpty(Q))
	{
		temp = Q -> front -> data;

		// Now check if the node is a leaf node
		if(temp -> left != NULL && temp -> right != NULL)
		{
			// This means a full node
			count++;
		}

		Q = deQueue(Q);
		if(temp -> left)
			Q = enQueue(Q, temp -> left);
		if(temp -> right)
			Q = enQueue(Q, temp -> right);
	}
	// Delete the queue
	free(Q);

	// Now return the count
	return count;
}

Time Complexity:- O(n)
Space Complexity:- O(n)

Ideone link for the sample program:- http://ideone.com/0C5baa

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More