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.

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Function to find level of given node x void Level(Node* root, Node* x, int index, int &level) { // return if tree is empty or level is already found if (root == nullptr || level) return; // if given node is found, update its level if (root == x) level = index; // recurse for left and right subtree Level(root->left, x, index + 1, level); Level(root->right, x, index + 1, level); } void printLevel(Node* root, Node *node, int level) { // base case if (root == nullptr) return; // print cousins if (level == 1) { cout << root->key << " "; return; } // recurse for left and right subtree if root is not parent // of given node if (root->left && root->left != node && root->right && root->right != node) { printLevel(root->left, node, level - 1); printLevel(root->right, node, level - 1); } } // Function to print all cousins of given node void printAllCousins(Node *root, Node *node) { int level = 0; // find level of given node Level(root, node, 1, level); // print all cousins of given node using its level number printLevel(root, node, level); } |

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

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.

Java implementation:

https://ideone.com/MvNM8Z