Given a Binary Tree, the task is to find the sum of all such nodes from the given tree whose sum of left and right subtree is either odd and even or even and odd respectively.
Examples:
Input:
11
/ \
23 44
/ \ / \
13 9 22 7
/ \
6 15
Output: 33
Explanation: There are only two such nodes:
- Node 22 having left subtree and right subtree sum as 6 (even) and 15(odd).
- Node 11 having left subtree and right subtree sum as 45 (odd) and 94 (even).
Therefore, the total sum = 22 + 11 = 33.
Input:
11
/
5
/ \
3 1
Output: 0
Explanation: There is no such node satisfying the given condition.
Approach: The idea is to recursively calculate the sum of the left subtree and the sum of the right subtree and then check for the given condition. Follow the steps below to solve the problem:
- Initialize a variable ans as 0 to store the sum of all such nodes.
- Perform the PostOrder Traversal in the given Tree.
- Find the sum of left and right subtree for each node and check if the sum are non-zero and check if sum of both the sums is odd or not. If found to be true, then include the current node value in ans.
- Return the sum of all the nodes of left subtree, right subtree, and current node value in each recursive calls.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h> using namespace std; // A binary tree nodestruct Node { int data; Node *left, *right; };/* Helper function that allocates a new node with the given data and NULL left and right pointers. */struct Node* newNode(int data){ struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return(node);} // Stores the desired result int mSum; // Function to find the sum of nodes // with subtree sums of opposite parities int getSum(Node *root) { // Return 0, if node is NULL if (root == NULL) return 0; // Recursively call left and // right subtree int lSum = getSum(root->left); int rSum = getSum(root->right); // Update mSum, if one subtree // sum is even and another is odd if (lSum != 0 && rSum != 0) if ((lSum + rSum) % 2 != 0) mSum += root->data; // Return the sum of subtree return lSum + rSum + root->data; } // Driver Code int main() { // Given number of nodes int n = 9; // Binary tree formation struct Node *root = newNode(11); root->left = newNode(23); root->right = newNode(44); root->left->left = newNode(13); root->left->right = newNode(9); root->right->left = newNode(22); root->right->right = newNode(7); root->right->left->left = newNode(6); root->right->left->right = newNode(15); // 11 // / \ // 23 44 // / \ / \ // 13 9 22 7 // / \ // 6 15 mSum = 0; getSum(root); // Print the sum cout<<(mSum); }// This code is contributed by 29AjayKumar |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;// A binary tree nodeclass Node { int data; Node left, right; // Constructor Node(int item) { data = item; left = right = null; }}// Binary Tree Classclass BinaryTree { // Stores the desired result static int mSum; Node root; // Function to find the sum of nodes // with subtree sums of opposite parities static int getSum(Node root) { // Return 0, if node is null if (root == null) return 0; // Recursively call left and // right subtree int lSum = getSum(root.left); int rSum = getSum(root.right); // Update mSum, if one subtree // sum is even and another is odd if (lSum != 0 && rSum != 0) if ((lSum + rSum) % 2 != 0) mSum += root.data; // Return the sum of subtree return lSum + rSum + root.data; } // Driver Code public static void main(String[] args) { // Given number of nodes int n = 9; BinaryTree tree = new BinaryTree(); // Binary tree formation tree.root = new Node(11); tree.root.left = new Node(23); tree.root.right = new Node(44); tree.root.left.left = new Node(13); tree.root.left.right = new Node(9); tree.root.right.left = new Node(22); tree.root.right.right = new Node(7); tree.root.right.left.left = new Node(6); tree.root.right.left.right = new Node(15); // 11 // / \ // 23 44 // / \ / \ // 13 9 22 7 // / \ // 6 15 mSum = 0; getSum(tree.root); // Print the sum System.out.println(mSum); }} |
Python3
# Python3 program for the above approach# A binary tree nodeclass Node: def __init__(self, x): self.data = x self.left = None self.right = None# Stores the desired resultmSum = 0# Function to find the sum of nodes# with subtree sums of opposite paritiesdef getSum(root): global mSum # Return 0, if node is None if (root == None): return 0 # Recursively call left and # right subtree lSum = getSum(root.left) rSum = getSum(root.right) # Update mSum, if one subtree # sum is even and another is odd if (lSum != 0 and rSum != 0): if ((lSum + rSum) % 2 != 0): mSum += root.data # Return the sum of subtree return lSum + rSum + root.data# Driver Codeif __name__ == '__main__': # Given number of nodes n = 9 # Binary tree formation root = Node(11) root.left = Node(23) root.right = Node(44) root.left.left = Node(13) root.left.right = Node(9) root.right.left = Node(22) root.right.right = Node(7) root.right.left.left = Node(6) root.right.left.right = Node(15) # 11 # / \ # 23 44 # / \ / \ #13 9 22 7 # / \ # 6 15 mSum = 0 getSum(root) # Print the sum print(mSum)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;// A binary tree nodepublic class Node{ public int data; public Node left, right; // Constructor public Node(int item) { data = item; left = right = null; }}// Binary Tree Classclass BinaryTree{// Stores the desired resultstatic int mSum;Node root;// Function to find the sum of nodes// with subtree sums of opposite paritiesstatic int getSum(Node root){ // Return 0, if node is null if (root == null) return 0; // Recursively call left and // right subtree int lSum = getSum(root.left); int rSum = getSum(root.right); // Update mSum, if one subtree // sum is even and another is odd if (lSum != 0 && rSum != 0) if ((lSum + rSum) % 2 != 0) mSum += root.data; // Return the sum of subtree return lSum + rSum + root.data;}// Driver Codepublic static void Main(String[] args){ // Given number of nodes //int n = 9; BinaryTree tree = new BinaryTree(); // Binary tree formation tree.root = new Node(11); tree.root.left = new Node(23); tree.root.right = new Node(44); tree.root.left.left = new Node(13); tree.root.left.right = new Node(9); tree.root.right.left = new Node(22); tree.root.right.right = new Node(7); tree.root.right.left.left = new Node(6); tree.root.right.left.right = new Node(15); // 11 // / \ // 23 44 // / \ / \ // 13 9 22 7 // / \ // 6 15 mSum = 0; getSum(tree.root); // Print the sum Console.WriteLine(mSum);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// A binary tree nodeclass Node{ constructor(item) { this.left = null; this.right = null; this.data = item; }}// Stores the desired resultlet mSum;let root;class BinaryTree{ constructor() { this.root = null; }}// Function to find the sum of nodes// with subtree sums of opposite paritiesfunction getSum(root){ // Return 0, if node is null if (root == null) return 0; // Recursively call left and // right subtree let lSum = getSum(root.left); let rSum = getSum(root.right); // Update mSum, if one subtree // sum is even and another is odd if (lSum != 0 && rSum != 0) if ((lSum + rSum) % 2 != 0) mSum += root.data; // Return the sum of subtree return lSum + rSum + root.data;}// Driver code// Given number of nodeslet n = 9;let tree = new BinaryTree();// Binary tree formationtree.root = new Node(11);tree.root.left = new Node(23);tree.root.right = new Node(44);tree.root.left.left = new Node(13);tree.root.left.right = new Node(9);tree.root.right.left = new Node(22);tree.root.right.right = new Node(7);tree.root.right.left.left = new Node(6);tree.root.right.left.right = new Node(15);// 11// / \// 23 44// / \ / \// 13 9 22 7// / \// 6 15mSum = 0;getSum(tree.root);// Print the sumdocument.write(mSum);// This code is contributed by divyeshrabadiya07</script> |
Output:
33
Time Complexity: O(N), where N is the number of nodes in the Binary Tree.
Auxiliary Space: O(1)
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!
