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 3 minutes read

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.


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);
		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

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

	// 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

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