Sunday, September 30, 2012

Nearest sibling of a node

Find the nearest sibling of a given node in a tree. Nodes on same level are siblings of each other.
_________A_________
_____B________C____
___D___E____H_____
__F_____G__I_______
Nearest sibling of G is I

Strategy:

Do breadth first traversal of a tree ..
For this, we need one FIFO queue . Starting from root of the tree, go on queuing nodes in a queue at each level, then dequeue the front node and enqueue it's children and so on ...
In above example,
1. Enqueue A - Queue = A
2. Dequeue A and Enqueue B and C - Queue = B C
3. Dequeue B and Enqueue D and E - Queue = C D E
4 .Dequeue C and Enqueue H - Queue = D E H
5. Dequeue D and Enqueue F - Queue = E H F
6. Dequeue E and Enqueue G - Queue = H F G
7. Dequeue H and Enqueue I - Queue = F G I
8. Dequeue F - Queue = G I
Hence, in the queue we can see that nearest sibling of G is I.

No comments:

Post a Comment