C++ program to check whether if two nodes are cousins in a binary tree
DESCRIPTION:
In this program we are checking if the two given nodes are cousins or not and it can be solved by performing level order traversal. The idea is to use a queue to perform level order traversal, in which each queue element is a pair of node and parent of that node. For each node visited in level order traversal, check if that node is either first given node or second given node. If any node is found store parent of that node. While performing level order traversal, one level is traversed at a time. If both nodes are found in given level, then their parent values are compared to check if they are siblings or not. If one node is found in given level and another is not found, then given nodes are not cousins.
Cousins nodes are the nodes which are same level but with the different parents. Nodes with same parents becomes siblings.
Example:
1
/ \
2 3
/ \ / \
4 5 6 7
Here we can see 4 and 7 are the cousin nodes
CODE:
// C++ program to check if two given nodes are cousins or not #include<iostream> #include<queue> using namespace std; //creating a new node struct Node { int data; struct Node *left, *right; }; struct Node* newNode(int item) //to assign space { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->data = item; temp->left = temp->right = NULL; return temp; } //function template to create binary tree Node* createTree() { //creating all nodes needed in the binary tree Node* node1 = new Node; node1->data = 1; Node* node2 = new Node; node2->data = 2; Node* node3 = new Node; node3->data = 3; Node* node4 = new Node; node4->data = 4; Node* node5 = new Node; node5->data = 5; Node* node6 = new Node; node6->data = 6; Node* node7 = new Node; node7->data = 7; //connecting nodes to create a binary tree node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; node3->left = node6; node3->right = node7; return node1; //returning the root node as it is connected to every node } bool Cousins(Node* root, Node* a, Node* b) { if (root == NULL) return false; Node *parentA= NULL ,*parentB = NULL; //storing parent of node a and b //queue to do level order traversal and every pair is a node and its parent queue<pair<Node*, Node*>> q; Node* tmp = newNode(-1); pair<Node*, Node*> data; // To store front datament of queue. q.push(make_pair(root, tmp)); // Push root to queue. int levSize; while (!q.empty()) //finding no. of nodes in the current level { levSize = q.size(); while (levSize) { data = q.front(); q.pop(); // check if current node is node a or node b or not. if (data.first->data == a->data) parentA= data.second; if (data.first->data == b->data) parentB = data.second; // push children of current node to queue. if (data.first->left) q.push(make_pair(data.first->left, data.first)); if (data.first->right) q.push(make_pair(data.first->right, data.first)); levSize--;
//if we found both the nodes then no need to traverse further if (parentA&& parentB)
break; } // Check if both nodes are siblings or not. if (parentA&& parentB) return parentA!= parentB; // if one node is found in the current level and other not found then
they are not cousins if ((parentA&& !parentB) || (parentB && !parentA)) return false; } return false; } int main() { Node* root = createTree(); //creating tree Cousins(root, root->left->left, root->right->right) ?
puts("Yes the given nodes are cousins") :
puts("No the given nodes are not cousins"); return 0; }
OUTPUT:
Comments