Given a binary search tree and a number N, the task is to find the sum of the cousins of the given node N if a node with given value ‘N’ is present in the given BST otherwise print -1.
Examples:
Input: Node = 12 Output: 40 Cousins are 18 and 22 Input: 19 Output: -1
Approach: Given below is the algorithm to solve the problem.
- Find the parent of the given node, if the node is not present return -1.
- Traverse in the tree, find the level of each node while traversal.
- If the level is the same as the given node. Check for the parent of that node, if the parent is different then add the node to the sum.
Below is the implementation of above approach:
C++
// C++ program to find the sum of cousins// of a node of a given BST#include <bits/stdc++.h>using namespace std;// structure to store the binary treestruct Tree { int data; struct Tree *left, *right;};// insertion of node in the binary treestruct Tree* newNode(int data){ // allocates memory struct Tree* node = (struct Tree*)malloc(sizeof(struct Tree)); // initializes data node->data = data; // marks the left and right // child as NULL node->left = node->right = NULL; // Return the node after allocating memory return (node);};// Function which calculates the sum of the cousin Nodeint SumOfCousin(struct Tree* root, int p, int level1, int level){ int sum = 0; if (root == NULL) return 0; // nodes which has same parent // as the given node will not be // taken to count for calculation if (p == root->data) return 0; // if the level is same // then it is a cousin // as parent checking has been // done above if (level1 == level) return root->data; // traverse in the tree left and right else sum += SumOfCousin(root->left, p, level1 + 1, level) + SumOfCousin(root->right, p, level1 + 1, level); return sum;}// Function that returns the parent nodeint ParentNode(struct Tree* root, int NodeData){ int parent = -1; // traverse the full Binary tree while (root != NULL) { // if node is found if (NodeData == root->data) break; // if less than move to left else if (NodeData < root->data) { parent = root->data; root = root->left; } // if greater than move to right else { parent = root->data; root = root->right; } } // Node not found if (root == NULL) return -1; else return parent;}// Function to find the level of the given nodeint LevelOfNode(struct Tree* root, int NodeData){ // calculate the level of node int level = 0; while (root != NULL) { // if the node is found if (NodeData == root->data) break; // move to the left of the tree if (NodeData < root->data) { root = root->left; } // move to the right of the tree else { root = root->right; } // increase the level after every traversal level++; } // return the level of a given node return level;}// Driver Codeint main(){ // initialize the root as NULL struct Tree* root = NULL; // Inserts node in the tree // tree is the same as the one in image root = newNode(15); root->left = newNode(13); root->left->left = newNode(12); root->left->right = newNode(14); root->right = newNode(20); root->right->left = newNode(18); root->right->right = newNode(22); // Given Node int NodeData = 12; int p, level, sum; // function call to find the parent node p = ParentNode(root, NodeData); // if given Node is not present then print -1 if (p == -1) cout << "-1\n"; // if present then find the level of the node // and call the sum of cousin function else { // function call to find the level of that node level = LevelOfNode(root, NodeData); // sum of cousin nodes of the given nodes sum = SumOfCousin(root, p, 0, level); // print the sum cout << sum; } return 0;} |
Java
// Java program to find the sum of cousins// of a node of a given BSTclass GFG{// structure to store the binary treestatic class Tree { int data; Tree left, right;};// insertion of node in the binary treestatic Tree newNode(int data){ // allocates memory Tree node = new Tree(); // initializes data node.data = data; // marks the left and right // child as null node.left = node.right = null; // Return the node after allocating memory return (node);}// Function which calculates // the sum of the cousin Nodestatic int SumOfCousin(Tree root, int p, int level1, int level){ int sum = 0; if (root == null) return 0; // nodes which has same parent // as the given node will not be // taken to count for calculation if (p == root.data) return 0; // if the level is same // then it is a cousin // as parent checking has been // done above if (level1 == level) return root.data; // traverse in the tree left and right else sum += SumOfCousin(root.left, p, level1 + 1, level) + SumOfCousin(root.right, p, level1 + 1, level); return sum;}// Function that returns the parent nodestatic int ParentNode(Tree root, int NodeData){ int parent = -1; // traverse the full Binary tree while (root != null) { // if node is found if (NodeData == root.data) break; // if less than move to left else if (NodeData < root.data) { parent = root.data; root = root.left; } // if greater than move to right else { parent = root.data; root = root.right; } } // Node not found if (root == null) return -1; else return parent;}// Function to find the level of the given nodestatic int LevelOfNode(Tree root, int NodeData){ // calculate the level of node int level = 0; while (root != null) { // if the node is found if (NodeData == root.data) break; // move to the left of the tree if (NodeData < root.data) { root = root.left; } // move to the right of the tree else { root = root.right; } // increase the level after every traversal level++; } // return the level of a given node return level;}// Driver Codepublic static void main(String[] args){ // initialize the root as null Tree root = null; // Inserts node in the tree // tree is the same as the one in image root = newNode(15); root.left = newNode(13); root.left.left = newNode(12); root.left.right = newNode(14); root.right = newNode(20); root.right.left = newNode(18); root.right.right = newNode(22); // Given Node int NodeData = 12; int p, level, sum; // function call to find the parent node p = ParentNode(root, NodeData); // if given Node is not present then print -1 if (p == -1) System.out.print("-1\n"); // if present then find the level of the node // and call the sum of cousin function else { // function call to find the level of that node level = LevelOfNode(root, NodeData); // sum of cousin nodes of the given nodes sum = SumOfCousin(root, p, 0, level); // print the sum System.out.print(sum); }}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the sum of cousins# of a node of a given BST# structure to store the binary treeclass newNode: def __init__(self, data): self.data = data self.left = None self.right = None# Function which calculates the # sum of the cousin Nodedef SumOfCousin(root, p, level1, level): sum = 0 if (root == None): return 0 # Nodes which has same parent # as the given node will not be # taken to count for calculation if (p == root.data): return 0 # If the level is same # then it is a cousin # as parent checking has been # done above if (level1 == level): return root.data # Traverse in the tree left and right else: sum += (SumOfCousin(root.left, p, level1 + 1, level) + SumOfCousin(root.right, p, level1 + 1, level)) return sum# Function that returns the parent nodedef ParentNode(root, NodeData): parent = -1 # Traverse the full Binary tree while (root != None): # If node is found if (NodeData == root.data): break # If less than move to left elif (NodeData < root.data): parent = root.data root = root.left # If greater than move to right else: parent = root.data root = root.right # Node not found if (root == None): return -1 else: return parent# Function to find the level of # the given nodedef LevelOfNode(root, NodeData): # Calculate the level of node level = 0 while (root != None): # If the node is found if (NodeData == root.data): break # Move to the left of the tree if (NodeData < root.data): root = root.left # Move to the right of the tree else: root = root.right # Increase the level after every traversal level += 1 # Return the level of a given node return level# Driver Codeif __name__ == '__main__': # Initialize the root as NULL root = None # Inserts node in the tree # tree is the same as the # one in image root = newNode(15) root.left = newNode(13) root.left.left = newNode(12) root.left.right = newNode(14) root.right = newNode(20) root.right.left = newNode(18) root.right.right = newNode(22) # Given Node NodeData = 12 # Function call to find the parent node p = ParentNode(root, NodeData) # If given Node is not present then print -1 if (p == -1): print("-1") # If present then find the level of the node # and call the sum of cousin function else: # Function call to find the # level of that node level = LevelOfNode(root, NodeData) # Sum of cousin nodes of the given nodes sum = SumOfCousin(root, p, 0, level) # Print the sum print(sum)# This code is contributed by bgangwar59 |
C#
// C# program to find the sum of cousins// of a node of a given BSTusing System;class GFG{// structure to store the binary treeclass Tree { public int data; public Tree left, right;};// insertion of node in the binary treestatic Tree newNode(int data){ // allocates memory Tree node = new Tree(); // initializes data node.data = data; // marks the left and right // child as null node.left = node.right = null; // Return the node after allocating memory return (node);}// Function which calculates // the sum of the cousin Nodestatic int SumOfCousin(Tree root, int p, int level1, int level){ int sum = 0; if (root == null) return 0; // nodes which has same parent // as the given node will not be // taken to count for calculation if (p == root.data) return 0; // if the level is same // then it is a cousin // as parent checking has been // done above if (level1 == level) return root.data; // traverse in the tree left and right else sum += SumOfCousin(root.left, p, level1 + 1, level) + SumOfCousin(root.right, p, level1 + 1, level); return sum;}// Function that returns the parent nodestatic int ParentNode(Tree root, int NodeData){ int parent = -1; // traverse the full Binary tree while (root != null) { // if node is found if (NodeData == root.data) break; // if less than move to left else if (NodeData < root.data) { parent = root.data; root = root.left; } // if greater than move to right else { parent = root.data; root = root.right; } } // Node not found if (root == null) return -1; else return parent;}// Function to find the level of the given nodestatic int LevelOfNode(Tree root, int NodeData){ // calculate the level of node int level = 0; while (root != null) { // if the node is found if (NodeData == root.data) break; // move to the left of the tree if (NodeData < root.data) { root = root.left; } // move to the right of the tree else { root = root.right; } // increase the level // after every traversal level++; } // return the level of a given node return level;}// Driver Codepublic static void Main(String[] args){ // initialize the root as null Tree root = null; // Inserts node in the tree // tree is the same as the one in image root = newNode(15); root.left = newNode(13); root.left.left = newNode(12); root.left.right = newNode(14); root.right = newNode(20); root.right.left = newNode(18); root.right.right = newNode(22); // Given Node int NodeData = 12; int p, level, sum; // function call to find the parent node p = ParentNode(root, NodeData); // if given Node is not present // then print -1 if (p == -1) Console.Write("-1\n"); // if present then find the level of the node // and call the sum of cousin function else { // function call to find the level of that node level = LevelOfNode(root, NodeData); // sum of cousin nodes of the given nodes sum = SumOfCousin(root, p, 0, level); // print the sum Console.Write(sum); }}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find the sum of // cousins of a node of a given BST// Structure to store the binary treeclass Tree{ constructor(data) { this.left = null; this.right = null; this.data = data; }}// Insertion of node in the binary treefunction newNode(data){ // Allocates memory let node = new Tree(data); // Return the node after // allocating memory return (node);}// Function which calculates// the sum of the cousin Nodefunction SumOfCousin(root, p, level1, level){ let sum = 0; if (root == null) return 0; // Nodes which has same parent // as the given node will not be // taken to count for calculation if (p == root.data) return 0; // If the level is same // then it is a cousin // as parent checking has been // done above if (level1 == level) return root.data; // Traverse in the tree left and right else sum += SumOfCousin(root.left, p, level1 + 1, level) + SumOfCousin(root.right, p, level1 + 1, level); return sum;}// Function that returns the parent nodefunction ParentNode(root, NodeData){ let parent = -1; // Traverse the full Binary tree while (root != null) { // If node is found if (NodeData == root.data) break; // If less than move to left else if (NodeData < root.data) { parent = root.data; root = root.left; } // If greater than move to right else { parent = root.data; root = root.right; } } // Node not found if (root == null) return -1; else return parent;}// Function to find the level of the given nodefunction LevelOfNode(root, NodeData){ // Calculate the level of node let level = 0; while (root != null) { // If the node is found if (NodeData == root.data) break; // Move to the left of the tree if (NodeData < root.data) { root = root.left; } // Move to the right of the tree else { root = root.right; } // Increase the level // after every traversal level++; } // Return the level of a given node return level;}// Driver code// Initialize the root as nulllet root = null;// Inserts node in the tree// tree is the same as the one in imageroot = newNode(15);root.left = newNode(13);root.left.left = newNode(12);root.left.right = newNode(14);root.right = newNode(20);root.right.left = newNode(18);root.right.right = newNode(22);// Given Nodelet NodeData = 12;let p, level, sum;// Function call to find the parent nodep = ParentNode(root, NodeData);// If given Node is not present// then print -1if (p == -1) document.write("-1" + "</br>");// If present then find the level of the node// and call the sum of cousin functionelse{ // Function call to find the level of that node level = LevelOfNode(root, NodeData); // Sum of cousin nodes of the given nodes sum = SumOfCousin(root, p, 0, level); // Print the sum document.write(sum);}// This code is contributed by divyeshrabadiya07</script> |
Output
40
The time complexity is O(h), where h is the height of the binary search tree. This is because in the worst case scenario, the program needs to traverse the entire height of the tree to find the given node, its parent, and its level. This is why the time complexity is proportional to the height of the tree.
The space complexity is O(h), where h is the height of the binary search tree. This is because the function calls are stored in the call stack, and the maximum number of function calls that can be stored in the call stack is proportional to the height of the tree.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
