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

_________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.

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