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.

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

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 58 59 60 61 62 63 64 65 66 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Data structure to store a Binary Tree node along // with its level and parent information struct NodeInfo { int key; int level; Node* parent; }; // Perform in-order traversal of the binary tree and update x and y void inorder(Node* root, Node *parent, int level, NodeInfo &x, NodeInfo &y) { // base case: tree is empty if (root == nullptr) return; // traverse left subtree inorder(root->left, root, level + 1, x, y); // if first element is found, save its level and parent node if (root->key == x.key) { x.level = level; x.parent = parent; } // if second element is found, save its level and parent node if (root->key == y.key) { y.level = level; y.parent = parent; } // traverse right subtree inorder(root->right, root, level + 1, x, y); } // Function to determine if two given nodes are cousins of each other bool iterative(Node* root, int elem1, int elem2) { // return if tree is empty if (root == nullptr) return true; int level = 1; // level of root is 1 Node* parent = nullptr; // parent of root is null NodeInfo x = {elem1, level, parent}; NodeInfo y = {elem2, level, parent}; // perform in-order traversal of the array and update x and y inorder(root, nullptr, 1, x, y); // return false if x and y have different level or same parent if (x.level != y.level || x.parent == y.parent) return false; return true; } |

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