Microsoft Question: Find the nearest sibling of a given node in a tree. Nodes on same level are siblings of each other

Solution:

Step 1: Do a preorder traversal of a tree and add sequence number corresponding to each node.

Step 2:  Now do a level order traversal of a tree and if a key appears in a level take the node with minimum difference in the sequence no with respect to the key, that will be the nearest sibling of the key.