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

Question

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 ?

What exactly do you mean by 'leaf nodes'? What are you trying to do? Where are you stuck? — letmutx, Mar 30 '17 at 09:12
Use a `while` loop to follow the left node, placing any right node in the queue. When you reach a leaf, resume with a node from the queue, until the queue is empty. — Weather Vane, Mar 30 '17 at 09:17
How leaf that are in the subtree of left node will be counted? — Sanya Pandey, Mar 30 '17 at 09:36
If you follow the left node, there is one and only one leaf. — Weather Vane, Mar 30 '17 at 09:38

score 1 · Answer 1 · answered Mar 30 '17 at 09:22

1

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

answered Mar 30 '17 at 09:22

letmutx

1,386
11
22

I dont know if I am wrong but I think it is still using recursion – Sanya Pandey Mar 30 '17 at 09:31
No, it doesn't. Where exactly do you see recursion? – letmutx Mar 30 '17 at 09:33
No, `queue.enqueue` is just like adding an element at the end of the array. See http://stackoverflow.com/questions/8722216/implementing-a-simple-queue-using-arrays#8722306 – letmutx Mar 30 '17 at 09:42
Ok yeah I understand its not. But if the right node is not null we enqueue it in a queue and after that what is going to happen? – Sanya Pandey Mar 30 '17 at 09:44
Understand how breadth first search works. Everything will be clear then. http://stackoverflow.com/questions/687731/breadth-first-vs-depth-first – letmutx Mar 30 '17 at 09:46
It is a kind of a traversal. You traverse the tree layer by layer top to bottom. – letmutx Mar 30 '17 at 10:03

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

1 Answers1