CODEWITHSUNDEEP
c
Sanya Pandey
Sanya Pandey

Reputation: 31

How to count number of leaf nodes in a binary tree using queue?

I am learning c language. It's Preety simple to count the leaf nodes in a binary treee using recursion but how can we do it using a queue ?

Upvotes: 0

Views: 549

Answers (1)

letmutx
letmutx

Reputation: 1416

Do a breadth first traversal of the tree using a queue and check if a particular node has both the children NULL.

Pseudocode:

queue = [root]
count = 0
while !queue.empty():
    current_node = queue.dequeue()
    if (current_node.left == NULL) and (current_node.right == NULL):
        count += 1
        continue
    if (current_node.left != NULL):
        queue.enqueue(current_node.left)
    if (current_node.right != NULL):
        queue.enqueue(current_node.right)

print count

Upvotes: 1

Related Questions