Given a binary tree containing n nodes. The problem is to find the sum of all the parent node’s which have a child node with value x.
Examples:
Input : Binary tree with x = 2:
4
/
2 5
/ /
7 2 2 3
Output : 11
4
/
2 5
/ /
7 2 2 3
The highlighted nodes (4, 2, 5) above
are the nodes having 2 as a child node.
Algorithm:
sumOfParentOfX(root,sum,x)
if root == NULL
return
if (root->left && root->left->data == x) ||
(root->right && root->right->data == x)
sum += root->data
sumOfParentOfX(root->left, sum, x)
sumOfParentOfX(root->right, sum, x)
sumOfParentOfXUtil(root,x)
Declare sum = 0
sumOfParentOfX(root, sum, x)
return sum
C++
// C++ implementation to find the sum of all // the parent nodes having child node x #include <bits/stdc++.h> using namespace std; // Node of a binary tree struct Node { int data; Node *left, *right; }; // function to get a new node Node* getNode(int data) { // allocate memory for the node Node *newNode = (Node*)malloc(sizeof(Node)); // put in the data newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // function to find the sum of all the // parent nodes having child node x void sumOfParentOfX(Node* root, int& sum, int x) { // if root == NULL if (!root) return; // if left or right child of root is 'x', then // add the root's data to 'sum' if ((root->left && root->left->data == x) || (root->right && root->right->data == x)) sum += root->data; // recursively find the required parent nodes // in the left and right subtree sumOfParentOfX(root->left, sum, x); sumOfParentOfX(root->right, sum, x); } // utility function to find the sum of all // the parent nodes having child node x int sumOfParentOfXUtil(Node* root, int x) { int sum = 0; sumOfParentOfX(root, sum, x); // required sum of parent nodes return sum; } // Driver program to test above int main() { // binary tree formation Node *root = getNode(4); /* 4 */ root->left = getNode(2); /* / */ root->right = getNode(5); /* 2 5 */ root->left->left = getNode(7); /* / / */ root->left->right = getNode(2); /* 7 2 2 3 */ root->right->left = getNode(2); root->right->right = getNode(3); int x = 2; cout << "Sum = " << sumOfParentOfXUtil(root, x); return 0; } |
Java
// Java implementation to find // the sum of all the parent // nodes having child node x class GFG { // sum static int sum = 0; // Node of a binary tree static class Node { int data; Node left, right; }; // function to get a new node static Node getNode(int data) { // allocate memory for the node Node newNode = new Node(); // put in the data newNode.data = data; newNode.left = newNode.right = null; return newNode; } // function to find the sum of all the // parent nodes having child node x static void sumOfParentOfX(Node root, int x) { // if root == NULL if (root == null) return; // if left or right child // of root is 'x', then // add the root's data to 'sum' if ((root.left != null && root.left.data == x) || (root.right != null && root.right.data == x)) sum += root.data; // recursively find the required // parent nodes in the left and // right subtree sumOfParentOfX(root.left, x); sumOfParentOfX(root.right, x); } // utility function to find the // sum of all the parent nodes // having child node x static int sumOfParentOfXUtil(Node root, int x) { sum = 0; sumOfParentOfX(root, x); // required sum of parent nodes return sum; } // Driver Code public static void main(String args[]) { // binary tree formation Node root = getNode(4); // 4 root.left = getNode(2); // / root.right = getNode(5); // 2 5 root.left.left = getNode(7); // / / root.left.right = getNode(2); // 7 2 2 3 root.right.left = getNode(2); root.right.right = getNode(3); int x = 2; System.out.println( "Sum = " + sumOfParentOfXUtil(root, x)); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation to find the Sum of
# all the parent nodes having child node x
# function to get a new node
class getNode:
def __init__(self, data):
# put in the data
self.data = data
self.left = self.right = None
# function to find the Sum of all the
# parent nodes having child node x
def SumOfParentOfX(root, Sum, x):
# if root == None
if (not root):
return
# if left or right child of root is ‘x’,
# then add the root’s data to ‘Sum’
if ((root.left and root.left.data == x) or
(root.right and root.right.data == x)):
Sum[0] += root.data
# recursively find the required parent
# nodes in the left and right subtree
SumOfParentOfX(root.left, Sum, x)
SumOfParentOfX(root.right, Sum, x)
# utility function to find the Sum of all
# the parent nodes having child node x
def SumOfParentOfXUtil(root, x):
Sum = [0]
SumOfParentOfX(root, Sum, x)
# required Sum of parent nodes
return Sum[0]
# Driver Code
if __name__ == ‘__main__’:
# binary tree formation
root = getNode(4) # 4
root.left = getNode(2) # /
root.right = getNode(5) # 2 5
root.left.left = getNode(7) # / /
root.left.right = getNode(2) # 7 2 2 3
root.right.left = getNode(2)
root.right.right = getNode(3)
x = 2
print(“Sum = “, SumOfParentOfXUtil(root, x))
# This code is contributed by PranchalK
C#
using System; // C# implementation to find // the sum of all the parent // nodes having child node x public class GFG { // sum public static int sum = 0; // Node of a binary tree public class Node { public int data; public Node left, right; } // function to get a new node public static Node getNode(int data) { // allocate memory for the node Node newNode = new Node(); // put in the data newNode.data = data; newNode.left = newNode.right = null; return newNode; } // function to find the sum of all the // parent nodes having child node x public static void sumOfParentOfX(Node root, int x) { // if root == NULL if (root == null) { return; } // if left or right child // of root is 'x', then // add the root's data to 'sum' if ((root.left != null && root.left.data == x) || (root.right != null && root.right.data == x)) { sum += root.data; } // recursively find the required // parent nodes in the left and // right subtree sumOfParentOfX(root.left, x); sumOfParentOfX(root.right, x); } // utility function to find the // sum of all the parent nodes // having child node x public static int sumOfParentOfXUtil(Node root, int x) { sum = 0; sumOfParentOfX(root, x); // required sum of parent nodes return sum; } // Driver Code public static void Main(string[] args) { // binary tree formation Node root = getNode(4); // 4 root.left = getNode(2); // / root.right = getNode(5); // 2 5 root.left.left = getNode(7); // / / root.left.right = getNode(2); // 7 2 2 3 root.right.left = getNode(2); root.right.right = getNode(3); int x = 2; Console.WriteLine("Sum = " + sumOfParentOfXUtil(root, x)); } } // This code is contributed by Shrikant13 |
Output:
Sum = 11
Time Complexity: O(n).
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments