Print cousins of given node in a binary tree

Given a binary tree, print all cousins of a given node. 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

 
level order traversal


6, 7 are cousins of node 4 or 5
4, 5 are cousins of node 6 or 7

 


 

The idea is to find level of given node in binary tree by doing a pre-order traversal of the tree. Once the level is found, we print all nodes present in that level which is not sibling of given node or the node itself.

 
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.
 

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)
Loading...

 
Thanks for reading.
 

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
MessiCR7
Guest

the part of the code where we are recursing for the left and right subtree if root is not the parent of the given node,
isnt the code not considering the case where a root might have left subtree only and no right subtree and vice versa? It seems like recurses for its child trees only if both are present which doesnt seem correct.

Vikky Agrawal
Guest

Java implementation:
https://ideone.com/MvNM8Z