Determine if given two nodes are cousins of each other

Given a binary tree, determine if two given nodes are cousins of each other or not. Two nodes of binary tree are cousins of each other only if they have different parents but they have same level.

 

For example, consider below tree

 
binary-tree


(4, 6), (4, 7), (5, 6) and (5, 7) are cousins of each other
(2, 3), (4, 5), (6, 7), (4, 3), etc are not cousins of each other

 


 

The idea is to search for given nodes in binary tree by doing an in-order traversal of the tree and store their level and parent node. Once both nodes are found, if they are present at same level and have different parents, they are cousins of each other. If their level are different or they are sibling of each other, they cannot be cousins.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz