Given a Binary Tree, the task is to find the sum of all the specially balanced nodes in the given Binary Tree.
A specially balanced node in a Binary Tree contains the sum of nodes of one subtree(either left or right) as even and the sum of the other subtree as odd.
The nodes having only one child or no child can never be a balanced node.
Examples:
Input: Below is the given Tree:
Output: 33
Explanation:
The specially balanced nodes are 11 and 22.
For Node 11:
The sum of left subtree is (23 + 13 + 9) = 45 which is Odd.
The sum of right subtree is (44 + 22 + 7 + 6 + 15) = 94 which is Even.
For Node 22:
The sum of left subtree is 6 which is Even.
The sum of right subtree is 15 which is Odd.
Therefore, the sum of specially balanced nodes is 11 + 22 = 33.Input: Below is the given Tree:
Output: 16
Explanation:
The specially balanced nodes are 4 and 12.
For Node 4:
The sum of left subtree is 2 which is Even.
The sum of right subtree is 3 which is Odd.
For Node 12:
The sum of left subtree is 17 which is Odd.
The sum of right subtree is (16 + 4 + 9 + 2 + 3) = 34 which is Even.
Therefore, the sum of specially balanced nodes is 4 + 12 = 16.
Approach: The idea is to perform DFS Traversal on the given Tree using recursion and update the final sum as per the given conditions. Follow the steps below:
- Initialize a totalSum as 0 which stores the sum of all specially balanced nodes.
- Perform the DFS Traversal on the given Tree and check for the following:
- If the node is a leaf node, then return the value of that node.
- Now, if the current node is not a leaf node, recursively traverse for the left and right subtree.
- Return the value of the sum of the left and right subtree with the current root value when each recursive call ends.
- Check if the returned sums satisfy the property of the specially balanced node. IF found to be true, add the current node value to totalSum.
- Print the value of totalSum after completing the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of Binary Treestruct Node { int data; Node *left, *right;};// Function to create a new nodeNode* newnode(int data){ Node* temp = new Node; temp->data = data; temp->left = NULL; temp->right = NULL; // Return the created node return temp;}// Function to insert a node in the treeNode* insert(string s, int i, int N, Node* root, Node* temp){ if (i == N) return temp; // Left insertion if (s[i] == 'L') root->left = insert(s, i + 1, N, root->left, temp); // Right insertion else root->right = insert(s, i + 1, N, root->right, temp); // Return the root node return root;}// Function to find sum of specially// balanced nodes in the Treeint SBTUtil(Node* root, int& sum){ // Base Case if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return root->data; // Find the left subtree sum int left = SBTUtil(root->left, sum); // Find the right subtree sum int right = SBTUtil(root->right, sum); // Condition of specially // balanced node if (root->left && root->right) { // Condition of specially // balanced node if ((left % 2 == 0 && right % 2 != 0) || (left % 2 != 0 && right % 2 == 0)) { sum += root->data; } } // Return the sum return left + right + root->data;}// Function to build the binary treeNode* build_tree(int R, int N, string str[], int values[]){ // Form root node of the tree Node* root = newnode(R); int i; // Insert nodes into tree for (i = 0; i < N - 1; i++) { string s = str[i]; int x = values[i]; // Create a new Node Node* temp = newnode(x); // Insert the node root = insert(s, 0, s.size(), root, temp); } // Return the root of the Tree return root;}// Function to find the sum of specially// balanced nodesvoid speciallyBalancedNodes( int R, int N, string str[], int values[]){ // Build Tree Node* root = build_tree(R, N, str, values); // Stores the sum of specially // balanced node int sum = 0; // Function Call SBTUtil(root, sum); // Print required sum cout << sum << " ";}// Driver Codeint main(){ // Given nodes int N = 7; // Given root int R = 12; // Given path info of nodes // from root string str[N - 1] = { "L", "R", "RL", "RR", "RLL", "RLR" }; // Given node values int values[N - 1] = { 17, 16, 4, 9, 2, 3 }; // Function Call speciallyBalancedNodes(R, N, str, values); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{ static int sum;//Structure of Binary Treestatic class Node { int data; Node left, right;};//Function to create a new nodestatic Node newnode(int data){ Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; // Return the created node return temp;}//Function to insert a node in the treestatic Node insert(String s, int i, int N, Node root, Node temp){ if (i == N) return temp; // Left insertion if (s.charAt(i) == 'L') root.left = insert(s, i + 1, N, root.left, temp); // Right insertion else root.right = insert(s, i + 1, N, root.right, temp); // Return the root node return root;}//Function to find sum of specially//balanced nodes in the Treestatic int SBTUtil(Node root){ // Base Case if (root == null) return 0; if (root.left == null && root.right == null) return root.data; // Find the left subtree sum int left = SBTUtil(root.left); // Find the right subtree sum int right = SBTUtil(root.right); // Condition of specially // balanced node if (root.left != null && root.right != null) { // Condition of specially // balanced node if ((left % 2 == 0 && right % 2 != 0) || (left % 2 != 0 && right % 2 == 0)) { sum += root.data; } } // Return the sum return left + right + root.data;}//Function to build the binary treestatic Node build_tree(int R, int N, String str[], int values[]){ // Form root node of the tree Node root = newnode(R); int i; // Insert nodes into tree for (i = 0; i < N - 1; i++) { String s = str[i]; int x = values[i]; // Create a new Node Node temp = newnode(x); // Insert the node root = insert(s, 0, s.length(), root, temp); } // Return the root of the Tree return root;}// Function to find the // sum of specially// balanced nodesstatic void speciallyBalancedNodes(int R, int N, String str[], int values[]){ // Build Tree Node root = build_tree(R, N, str, values); // Stores the sum of specially // balanced node sum = 0; // Function Call SBTUtil(root); // Print required sum System.out.print(sum + " ");}//Driver Codepublic static void main(String[] args){ // Given nodes int N = 7; // Given root int R = 12; // Given path info of nodes // from root String str[] = {"L", "R", "RL", "RR", "RLL", "RLR"}; // Given node values int values[] = {17, 16, 4, 9, 2, 3}; // Function Call speciallyBalancedNodes(R, N, str, values);}}//This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Structure of Binary Treeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to create a new nodedef newnode(data): temp = Node(data) # Return the created node return temp# Function to insert a node in the treedef insert(s, i, N, root, temp): if (i == N): return temp # Left insertion if (s[i] == 'L'): root.left = insert(s, i + 1, N, root.left, temp) # Right insertion else: root.right = insert(s, i + 1, N, root.right, temp) # Return the root node return root# Function to find sum of specially# balanced nodes in the Treedef SBTUtil(root, sum): # Base Case if (root == None): return [0, sum] if (root.left == None and root.right == None): return [root.data, sum] # Find the left subtree sum left, sum = SBTUtil(root.left, sum) # Find the right subtree sum right, sum = SBTUtil(root.right, sum) # Condition of specially # balanced node if (root.left and root.right): # Condition of specially # balanced node if ((left % 2 == 0 and right % 2 != 0) or (left % 2 != 0 and right % 2 == 0)): sum += root.data # Return the sum return [left + right + root.data, sum]# Function to build the binary treedef build_tree(R, N, str, values): # Form root node of the tree root = newnode(R) # Insert nodes into tree for i in range(0, N - 1): s = str[i] x = values[i] # Create a new Node temp = newnode(x) # Insert the node root = insert(s, 0, len(s), root, temp) # Return the root of the Tree return root# Function to find the sum of specially# balanced nodesdef speciallyBalancedNodes(R, N, str, values): # Build Tree root = build_tree(R, N, str, values) # Stores the sum of specially # balanced node sum = 0 # Function Call tmp, sum = SBTUtil(root, sum) # Print required sum print(sum, end = ' ')# Driver codeif __name__ == "__main__": # Given nodes N = 7 # Given root R = 12 # Given path info of nodes # from root str = [ "L", "R", "RL", "RR", "RLL", "RLR" ] # Given node values values = [ 17, 16, 4, 9, 2, 3 ] # Function Call speciallyBalancedNodes(R, N, str, values)# This code is contributed by rutvik_56 |
C#
//C# program for // the above approachusing System;class GFG{ static int sum;//Structure of Binary Treeclass Node { public int data; public Node left, right;};//Function to create a new nodestatic Node newnode(int data){ Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; // Return the created node return temp;}//Function to insert a node in the treestatic Node insert(String s, int i, int N, Node root, Node temp){ if (i == N) return temp; // Left insertion if (s[i] == 'L') root.left = insert(s, i + 1, N, root.left, temp); // Right insertion else root.right = insert(s, i + 1, N, root.right, temp); // Return the root node return root;}//Function to find sum of specially//balanced nodes in the Treestatic int SBTUtil(Node root){ // Base Case if (root == null) return 0; if (root.left == null && root.right == null) return root.data; // Find the left subtree sum int left = SBTUtil(root.left); // Find the right subtree sum int right = SBTUtil(root.right); // Condition of specially // balanced node if (root.left != null && root.right != null) { // Condition of specially // balanced node if ((left % 2 == 0 && right % 2 != 0) || (left % 2 != 0 && right % 2 == 0)) { sum += root.data; } } // Return the sum return left + right + root.data;}//Function to build the binary treestatic Node build_tree(int R, int N, String []str, int []values){ // Form root node of the tree Node root = newnode(R); int i; // Insert nodes into tree for (i = 0; i < N - 1; i++) { String s = str[i]; int x = values[i]; // Create a new Node Node temp = newnode(x); // Insert the node root = insert(s, 0, s.Length, root, temp); } // Return the root of the Tree return root;}// Function to find the // sum of specially// balanced nodesstatic void speciallyBalancedNodes(int R, int N, String []str, int []values){ // Build Tree Node root = build_tree(R, N, str, values); // Stores the sum of specially // balanced node sum = 0; // Function Call SBTUtil(root); // Print required sum Console.Write(sum + " ");}//Driver Codepublic static void Main(String[] args){ // Given nodes int N = 7; // Given root int R = 12; // Given path info of nodes // from root String []str = {"L", "R", "RL", "RR", "RLL", "RLR"}; // Given node values int []values = {17, 16, 4, 9, 2, 3}; // Function Call speciallyBalancedNodes(R, N, str, values);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approachlet sum;// Structure of Binary Treeclass Node{ constructor(data) { this.left = null; this.right = null; this.data = data; }}// Function to create a new nodefunction newnode(data){ let temp = new Node(data); // Return the created node return temp;}// Function to insert a node in the treefunction insert(s, i, N, root, temp){ if (i == N) return temp; // Left insertion if (s[i] == 'L') root.left = insert(s, i + 1, N, root.left, temp); // Right insertion else root.right = insert(s, i + 1, N, root.right, temp); // Return the root node return root;}// Function to find sum of specially// balanced nodes in the Treefunction SBTUtil(root){ // Base Case if (root == null) return 0; if (root.left == null && root.right == null) return root.data; // Find the left subtree sum let left = SBTUtil(root.left); // Find the right subtree sum let right = SBTUtil(root.right); // Condition of specially // balanced node if (root.left != null && root.right != null) { // Condition of specially // balanced node if ((left % 2 == 0 && right % 2 != 0) || (left % 2 != 0 && right % 2 == 0)) { sum += root.data; } } // Return the sum return left + right + root.data;}// Function to build the binary treefunction build_tree(R, N, str, values){ // Form root node of the tree let root = newnode(R); let i; // Insert nodes into tree for(i = 0; i < N - 1; i++) { let s = str[i]; let x = values[i]; // Create a new Node let temp = newnode(x); // Insert the node root = insert(s, 0, s.length, root, temp); } // Return the root of the Tree return root;}// Function to find the// sum of specially// balanced nodesfunction speciallyBalancedNodes(R, N, str, values){ // Build Tree let root = build_tree(R, N, str, values); // Stores the sum of specially // balanced node sum = 0; // Function Call SBTUtil(root); // Print required sum document.write(sum + " ");}// Driver code// Given nodeslet N = 7;// Given rootlet R = 12;// Given path info of nodes// from rootlet str = [ "L", "R", "RL", "RR", "RLL", "RLR" ];// Given node valueslet values = [ 17, 16, 4, 9, 2, 3 ];// Function CallspeciallyBalancedNodes(R, N, str, values);// This code is contributed by suresh07</script> |
Output:
16
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
