Sum of all the parent nodes having child node x

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.
```

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` ` `  `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).

Tree Tree