Determine whether the given binary tree 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 a binary tree are cousins of each other only if they have different parents, but they are at the same level.
For example, consider the following 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.
(2, 3), (4, 5), (6, 7), (4, 3), etc., are not cousins of each other.
The idea is to search for given nodes in a binary tree by doing inorder traversal on the tree and store their level and parent node. If both nodes are present at the same level and have different parents, they are cousins. If their level is different, or they are a sibling, they cannot be cousins.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int key; Node *left, *right; Node(int key) { this->key = key; this->left = this->right = nullptr; } }; // Data structure to store a binary tree node along // with its level and parent information struct NodeInfo { Node* node; int level; Node* parent; }; // Perform inorder traversal on a given binary tree and update 'x' and 'y' void updateLevelandParent(Node* root, Node* parent, int level, NodeInfo &x, NodeInfo &y) { // base case: tree is empty if (root == nullptr) { return; } // traverse left subtree updateLevelandParent(root->left, root, level + 1, x, y); // if the first element is found, save its level and parent node if (root == x.node) { x.level = level; x.parent = parent; } // if the second element is found, save its level and parent node if (root == y.node) { y.level = level; y.parent = parent; } // traverse right subtree updateLevelandParent(root->right, root, level + 1, x, y); } // Function to determine if two given nodes are cousins of each other bool checkCousins(Node* root, Node* node1, Node* node2) { // return if the tree is empty if (root == nullptr) { return false; } int level = 1; // level of the root is 1 Node* parent = nullptr; // parent of the root is null NodeInfo x = {node1, level, parent}; NodeInfo y = {node2, level, parent}; // perform inorder traversal on the array and update 'x' and 'y' updateLevelandParent(root, nullptr, 1, x, y); // return true if 'x' and 'y' are at the same level, but different parent return x.level == y.level && x.parent != y.parent; } int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); if (checkCousins(root, root->left->right, root->right->left)) { cout << "Nodes are cousins of each other"; } else { cout << "Nodes are not cousins of each other"; } return 0; } |
Output:
Nodes are cousins of each other
Java
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
// A class to store a binary tree node class Node { int key; Node left = null, right = null; Node(int key) { this.key = key; } } class Main { // Data structure to store a binary tree node along // with its level and parent information static class NodeInfo { Node node = null; int level; Node parent = null; NodeInfo(Node node, int level, Node parent) { this.node = node; this.level = level; this.parent = parent; } } // Perform inorder traversal on a given binary tree and update 'x' and 'y' public static void updateLevelandParent(Node root, Node parent, int level, NodeInfo x, NodeInfo y) { // base case: tree is empty if (root == null) { return; } // traverse left subtree updateLevelandParent(root.left, root, level + 1, x, y); // if the first element is found, save its level and parent node if (root == x.node) { x.level = level; x.parent = parent; } // if the second element is found, save its level and parent node if (root == y.node) { y.level = level; y.parent = parent; } // traverse right subtree updateLevelandParent(root.right, root, level + 1, x, y); } // Function to determine if two given nodes are cousins of each other public static boolean checkCousins(Node root, Node node1, Node node2) { // return if the tree is empty if (root == null) { return false; } int level = 1; // level of the root is 1 Node parent = null; // parent of the root is null NodeInfo x = new NodeInfo(node1, level, parent); NodeInfo y = new NodeInfo(node2, level, parent); // perform inorder traversal on the array and update 'x' and 'y' updateLevelandParent(root, null, 1, x, y); // return true if 'x' and 'y' are at the same level, but different parent return x.level == y.level && x.parent != y.parent; } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); if (checkCousins(root, root.left.right, root.right.left)) { System.out.println("Nodes are cousins of each other"); } else { System.out.println("Nodes are not cousins of each other"); } } } |
Output:
Nodes are cousins of each other
Python
|
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 67 68 69 70 71 72 73 74 75 |
# A class to store a binary tree node class Node: def __init__(self, key, left=None, right=None): self.key = key self.left = left self.right = right # A class to store a binary tree node along with its level and parent information class NodeInfo: def __init__(self, node, level, parent): self.node = node self.level = level self.parent = parent # Perform inorder traversal on a given binary tree and update 'x' and 'y' def updateLevelandParent(root, x, y, parent=None, level=1): # base case: tree is empty if root is None: return # traverse left subtree updateLevelandParent(root.left, x, y, root, level + 1) # if the first element is found, save its level and parent node if root == x.node: x.level = level x.parent = parent # if the second element is found, save its level and parent node if root == y.node: y.level = level y.parent = parent # traverse right subtree updateLevelandParent(root.right, x, y, root, level + 1) # Function to determine if two given nodes are cousins of each other def checkCousins(root, node1, node2): # return if the tree is empty if root is None: return False level = 1 # level of the root is 1 parent = None # parent of the root is None x = NodeInfo(node1, level, parent) y = NodeInfo(node2, level, parent) # perform inorder traversal on the list and update 'x' and 'y' updateLevelandParent(root, x, y) # return true if 'x' and 'y' are at the same level, but different parent return x.level == y.level and x.parent != y.parent if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) if checkCousins(root, root.left.right, root.right.left): print('Nodes are cousins of each other') else: print('Nodes are not cousins of each other') |
Output:
Nodes are cousins of each other
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h is the height of the tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)