Sum of all the levels in a Binary Search Tree
Given a Binary Search Tree, the task is to find the horizontal sum of the nodes that are at the same level.
Examples:
Input:
Output:
6
12
24
Input:
Output:
6
12
12
Approach DFS: Find the height of the given binary tree then the number of levels in the tree will be levels = height + 1. Now create an array sum[] of size levels where sum[i] will store the sum of all the nodes at the ith level. To update this array, write a recursive function that adds the current node’s data at sum[level] where the level is the level of the current node and then recursively call the same method for the child nodes with level as level + 1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> #include <queue> using namespace std; // A Binary Tree Node struct Node { int data; struct Node *left, *right; }; // Utility function to create a new tree node Node* newNode( int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Utility function to print // the contents of an array void printArr( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << endl; } // Function to return the height // of the binary tree int getHeight(Node* root) { if (root->left == NULL && root->right == NULL) return 0; int left = 0; if (root->left != NULL) left = getHeight(root->left); int right = 0; if (root->right != NULL) right = getHeight(root->right); return (max(left, right) + 1); } // Recursive function to update sum[] array // such that sum[i] stores the sum // of all the elements at ith level void calculateLevelSum(Node* node, int level, int sum[]) { if (node == NULL) return ; // Add current node data to the sum // of the current node's level sum[level] += node->data; // Recursive call for left and right sub-tree calculateLevelSum(node->left, level + 1, sum); calculateLevelSum(node->right, level + 1, sum); } // Driver code int main() { // Create the binary tree Node* root = newNode(6); root->left = newNode(4); root->right = newNode(8); root->left->left = newNode(3); root->left->right = newNode(5); root->right->left = newNode(7); root->right->right = newNode(9); // Count of levels in the // given binary tree int levels = getHeight(root) + 1; // To store the sum at every level int sum[levels] = { 0 }; calculateLevelSum(root, 0, sum); // Print the required sums printArr(sum, levels); return 0; } |
Java
// Java implementation of the approach class Sol { // A Binary Tree Node static class Node { int data; Node left, right; }; // Utility function to create a new tree node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Utility function to print // the contents of an array static void printArr( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i]+ " " ); } // Function to return the height // of the binary tree static int getHeight(Node root) { if (root.left == null && root.right == null ) return 0 ; int left = 0 ; if (root.left != null ) left = getHeight(root.left); int right = 0 ; if (root.right != null ) right = getHeight(root.right); return (Math.max(left, right) + 1 ); } // Recursive function to update sum[] array // such that sum[i] stores the sum // of all the elements at ith level static void calculateLevelSum(Node node, int level, int sum[]) { if (node == null ) return ; // Add current node data to the sum // of the current node's level sum[level] += node.data; // Recursive call for left and right sub-tree calculateLevelSum(node.left, level + 1 , sum); calculateLevelSum(node.right, level + 1 , sum); } // Driver code public static void main(String args[]) { // Create the binary tree Node root = newNode( 6 ); root.left = newNode( 4 ); root.right = newNode( 8 ); root.left.left = newNode( 3 ); root.left.right = newNode( 5 ); root.right.left = newNode( 7 ); root.right.right = newNode( 9 ); // Count of levels in the // given binary tree int levels = getHeight(root) + 1 ; // To store the sum at every level int sum[]= new int [levels]; calculateLevelSum(root, 0 , sum); // Print the required sums printArr(sum, levels); } } // This code is contributed by andrew1234 |
Python3
# Python3 implementation of above algorithm # Utility class to create a node class Node: def __init__( self , key): self .data = key self .left = self .right = None # Utility function to create a tree node def newNode( data): temp = Node( 0 ) temp.data = data temp.left = temp.right = None return temp # Utility function to print # the contents of an array def printArr(arr, n): i = 0 while ( i < n): print ( arr[i]) i = i + 1 # Function to return the height # of the binary tree def getHeight(root): if (root.left = = None and root.right = = None ): return 0 left = 0 if (root.left ! = None ): left = getHeight(root.left) right = 0 if (root.right ! = None ): right = getHeight(root.right) return ( max (left, right) + 1 ) sum = [] # Recursive function to update sum[] array # such that sum[i] stores the sum # of all the elements at ith level def calculateLevelSum(node, level): global sum if (node = = None ): return # Add current node data to the sum # of the current node's level sum [level] + = node.data # Recursive call for left and right sub-tree calculateLevelSum(node.left, level + 1 ) calculateLevelSum(node.right, level + 1 ) # Driver code # Create the binary tree root = newNode( 6 ) root.left = newNode( 4 ) root.right = newNode( 8 ) root.left.left = newNode( 3 ) root.left.right = newNode( 5 ) root.right.left = newNode( 7 ) root.right.right = newNode( 9 ) # Count of levels in the # given binary tree levels = getHeight(root) + 1 # To store the sum at every level sum = [ 0 ] * levels calculateLevelSum(root, 0 ) # Print the required sums printArr( sum , levels) # This code is contributed by Arnab Kundu |
C#
// C# implementation of the approach using System; class GFG { // A Binary Tree Node public class Node { public int data; public Node left, right; }; // Utility function to create a new tree node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Utility function to print // the contents of an array static void printArr( int []arr, int n) { for ( int i = 0; i < n; i++) Console.WriteLine(arr[i]); } // Function to return the height // of the binary tree static int getHeight(Node root) { if (root.left == null && root.right == null ) return 0; int left = 0; if (root.left != null ) left = getHeight(root.left); int right = 0; if (root.right != null ) right = getHeight(root.right); return (Math.Max(left, right) + 1); } // Recursive function to update sum[] array // such that sum[i] stores the sum // of all the elements at ith level static void calculateLevelSum(Node node, int level, int []sum) { if (node == null ) return ; // Add current node data to the sum // of the current node's level sum[level] += node.data; // Recursive call for left and right sub-tree calculateLevelSum(node.left, level + 1, sum); calculateLevelSum(node.right, level + 1, sum); } // Driver code public static void Main(String []args) { // Create the binary tree Node root = newNode(6); root.left = newNode(4); root.right = newNode(8); root.left.left = newNode(3); root.left.right = newNode(5); root.right.left = newNode(7); root.right.right = newNode(9); // Count of levels in the // given binary tree int levels = getHeight(root) + 1; // To store the sum at every level int []sum = new int [levels]; calculateLevelSum(root, 0, sum); // Print the required sums printArr(sum, levels); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // A Binary Tree Node class Node { constructor(data) { this .data = data; this .left = this .right = null ; } } // Utility function to print // the contents of an array function printArr(arr, n) { for (let i = 0; i < n; i++) document.write(arr[i]+ " <br>" ); } // Function to return the height // of the binary tree function getHeight(root) { if (root.left == null && root.right == null ) return 0; let left = 0; if (root.left != null ) left = getHeight(root.left); let right = 0; if (root.right != null ) right = getHeight(root.right); return (Math.max(left, right) + 1); } // Recursive function to update sum[] array // such that sum[i] stores the sum // of all the elements at ith level function calculateLevelSum(node,level,sum) { if (node == null ) return ; // Add current node data to the sum // of the current node's level sum[level] += node.data; // Recursive call for left and right sub-tree calculateLevelSum(node.left, level + 1, sum); calculateLevelSum(node.right, level + 1, sum); } // Driver code // Create the binary tree let root = new Node(6); root.left = new Node(4); root.right = new Node(8); root.left.left = new Node(3); root.left.right = new Node(5); root.right.left = new Node(7); root.right.right = new Node(9); // Count of levels in the // given binary tree let levels = getHeight(root) + 1; // To store the sum at every level let sum= new Array(levels); for (let i = 0; i < levels; i++) sum[i] = 0; calculateLevelSum(root, 0, sum); // Print the required sums printArr(sum, levels); // This code is contributed by avanitrachhadiya2155 </script> |
6 12 24
Time Complexity : O(N)
Auxiliary Space: O(N)
Approach BFS:-Find the height of the given binary tree then the number of levels in the tree will level = height + 1. Now create an array sum[] of size levels where sum[i] will store the sum of all the nodes at the ith level. To update this array Using Breadth-First Search We Will calculate the sum at That Level with Queue and Add their children for future Levels
C++
#include<bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { int data; Node *left, *right; Node( int data) { this ->data = data; left = right = NULL; } }; // Utility function to print // the contents of an array void printArr( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Function to return the height // of the binary tree int getHeight(Node *root) { if (root == NULL) return 0; int left = 0; if (root->left != NULL) left = getHeight(root->left); int right = 0; if (root->right != NULL) right = getHeight(root->right); return (max(left, right) + 1); } // Function to Calculate Level Sum Using BFS void calculateLevelSum_Using_BFS(Node *root, int sum[]) { // Queue Through Which We Will Travel Tree Level // Wise queue<Node*> q; // Stores The CurrentLevel for Which is // Calculating Sum int current_level = 0; // Add root Node to queue q.push(root); // Travel queue while (!q.empty()) { // Stores the No. of Nodes at Current Level int no_of_nodes_current_level = q.size(); // Will store the LevelSum of CurrentLevel int current_LevelSum = 0; // Traveling all node of current level for ( int i = 0; i < no_of_nodes_current_level; i++) { Node * remove = q.front(); q.pop(); current_LevelSum += remove ->data; // Adding left node of next level if exist if ( remove ->left != NULL) { q.push( remove ->left); } // Adding right node of next level if exist if ( remove ->right != NULL) { q.push( remove ->right); } } // Assign Value of current Level Sum to Sum // arr sum[current_level] = current_LevelSum; // Increasing Level for next Iteration current_level++; } } int main() { // Creating Tree Node *root = new Node(6); root->left = new Node(4); root->right = new Node(8); root->left->left = new Node(3); root->left->right = new Node(5); root->right->left = new Node(7); root->right->right = new Node(9); // Finding How Many Level Does The Tree Have int levels = getHeight(root); int sum[levels]; // Calling The Function calculateLevelSum_Using_BFS(root, sum); // Printing the Array printArr(sum, levels); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.LinkedList; import java.util.Queue; // A Binary Tree Node class Node { int data; Node left, right; Node( int data) { this .data = data; left = null ; right = null ; } } public class GFG { // Utility function to create a new tree node static Node newNode( int data) { Node temp = new Node(data); temp.data = data; temp.left = temp.right = null ; return temp; } // Utility function to print // the contents of an array static void printArr( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Function to return the height // of the binary tree static int getHeight(Node root) { if (root.left == null && root.right == null ) return 0 ; int left = 0 ; if (root.left != null ) left = getHeight(root.left); int right = 0 ; if (root.right != null ) right = getHeight(root.right); return (Math.max(left, right) + 1 ); } // Function to Calculate Level Sum Using BFS static void calculateLevelSum_Using_BFS(Node root, int sum[]) { // Queue Through Which We Will Travel Tree Level // Wise Queue<Node> queue = new LinkedList<>(); // Stores The CurrentLevel for Which is // Calculating Sum int cureentlevel = 0 ; // Add root Node to queue queue.add(root); // Travel queue while (queue.size() > 0 ) { // Stores the No. of Nodes at Current Level int no_of_nodes_current_Level = queue.size(); // Will store the LevelSum of CurrentLevel int current_LevelSum = 0 ; // Traveling all node of current level for ( int i = 0 ; i < no_of_nodes_current_Level; i++) { Node remove = queue.poll(); current_LevelSum += remove.data; // Adding left node of next level if exist if (remove.left != null ) { queue.add(remove.left); } // Adding right node of next level if exist if (remove.right != null ) { queue.add(remove.right); } } // Assig Value of current Level Sum to Sum // arr sum[cureentlevel] = current_LevelSum; // Increasing Level for next Iteration cureentlevel++; } } public static void main(String[] args) { // Creating Tree Node root = newNode( 6 ); root.left = newNode( 4 ); root.right = newNode( 8 ); root.left.left = newNode( 3 ); root.left.right = newNode( 5 ); root.right.left = newNode( 7 ); root.right.right = newNode( 9 ); // Finding How Many Level Does The Tree Have int levels = getHeight(root) + 1 ; int sum[] = new int [levels]; // Calling The Function calculateLevelSum_Using_BFS(root, sum); // Printing the Array printArr(sum, levels); } // This Code is Contributed By Vikas Bishnoi } |
Python3
#Node constructor class Node: def __init__( self , key): self .data = key self .left = self .right = None # Utility function to create a tree node def newNode( data): temp = Node( 0 ) temp.data = data temp.left = temp.right = None return temp #function to print output array def printArr(arr, n): i = 0 while ( i < n): print ( arr[i]) i = i + 1 #function to get height at that particular level def getHeight(root): if (root.left = = None and root.right = = None ): return 0 left = 0 if (root.left ! = None ): left = getHeight(root.left) right = 0 if (root.right ! = None ): right = getHeight(root.right) return ( max (left, right) + 1 ) def calculateLevelSum_Using_BFS(root, sum ): # Queue Through Which We Will Travel Tree Level # Wise queue = [] # Stores The CurrentLevel for Which is # Calculating Sum cureentlevel = 0 # Add root Node to queue queue.append(root) while len (queue) > 0 : # Stores the No. of Nodes at Current Level no_of_nodes_current_Level = len (queue) # Will store the LevelSum of CurrentLevel current_LevelSum = 0 # Traveling all node of current level for i in range (no_of_nodes_current_Level): remove = queue.pop( 0 ) current_LevelSum + = remove.data # Adding left node of next level if exist if remove.left is not None : queue.append(remove.left) # Adding right node of next level if exist if remove.right is not None : queue.append(remove.right) # Assigning Value of current Level Sum to Sum # arr sum [cureentlevel] = current_LevelSum # Increasing Level for next Iteration cureentlevel + = 1 # Creating Tree root = newNode( 6 ) root.left = newNode( 4 ) root.right = newNode( 8 ) root.left.left = newNode( 3 ) root.left.right = newNode( 5 ) root.right.left = newNode( 7 ) root.right.right = newNode( 9 ) # Finding How Many Level Does The Tree Have levels = getHeight(root) + 1 sum = [ 0 ] * levels # Calling The Function calculateLevelSum_Using_BFS(root, sum ) # Printing the Array printArr( sum , levels) #This code is contributed by Tejas Gundale |
Javascript
// A Binary Tree Node class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Utility function to print the contents of an array function printArr(arr, n) { for (let i = 0; i < n; i++) { console.log(arr[i] + " " ); } } // Function to return the height of the binary tree function getHeight(root) { if (root == null ) { return 0; } let left = 0; if (root.left != null ) { left = getHeight(root.left); } let right = 0; if (root.right != null ) { right = getHeight(root.right); } return Math.max(left, right) + 1; } // Function to Calculate Level Sum Using BFS function calculateLevelSum_Using_BFS(root, sum) { // Queue Through Which We Will Travel Tree Level Wise let q = []; // Stores The CurrentLevel for Which is Calculating Sum let currentLevel = 0; // Add root Node to queue q.push(root); // Travel queue while (q.length > 0) { // Stores the No. of Nodes at Current Level let noOfNodesCurrentLevel = q.length; // Will store the LevelSum of CurrentLevel let currentLevelSum = 0; // Traveling all node of current level for (let i = 0; i < noOfNodesCurrentLevel; i++) { let remove = q.shift(); currentLevelSum += remove.data; // Adding left node of next level if exist if (remove.left != null ) { q.push(remove.left); } // Adding right node of next level if exist if (remove.right != null ) { q.push(remove.right); } } // Assign Value of current Level Sum to Sum arr sum[currentLevel] = currentLevelSum; // Increasing Level for next Iteration currentLevel++; } } // driver program to test above functions // Creating Tree let root = new Node(6); root.left = new Node(4); root.right = new Node(8); root.left.left = new Node(3); root.left.right = new Node(5); root.right.left = new Node(7); root.right.right = new Node(9); // Finding How Many Level Does The Tree Have let levels = getHeight(root); let sum = new Array(levels); // Calling The Function calculateLevelSum_Using_BFS(root, sum); // Printing the Array printArr(sum, levels); |
C#
using System; using System.Collections.Generic; // A Binary Tree Node class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = null ; right = null ; } } public class GFG { // Utility function to create a new tree node static Node newNode( int data) { Node temp = new Node(data); temp.data = data; temp.left = temp.right = null ; return temp; } // Utility function to print // the contents of an array static void printArr( int [] arr, int n) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Function to return the height // of the binary tree static int getHeight(Node root) { if (root.left == null && root.right == null ) return 0; int left = 0; if (root.left != null ) left = getHeight(root.left); int right = 0; if (root.right != null ) right = getHeight(root.right); return (Math.Max(left, right) + 1); } // Function to Calculate Level Sum Using BFS static void calculateLevelSum_Using_BFS(Node root, int [] sum) { // Queue Through Which We Will Travel Tree Level // Wise Queue<Node> queue = new Queue<Node>(); // Stores The CurrentLevel for Which is // Calculating Sum int currentLevel = 0; // Add root Node to queue queue.Enqueue(root); // Travel queue while (queue.Count > 0) { // Stores the No. of Nodes at Current Level int no_of_nodes_current_Level = queue.Count; // Will store the LevelSum of CurrentLevel int current_LevelSum = 0; // Traveling all node of current level for ( int i = 0; i < no_of_nodes_current_Level; i++) { Node remove = queue.Dequeue(); current_LevelSum += remove.data; // Adding left node of next level if exist if (remove.left != null ) { queue.Enqueue(remove.left); } // Adding right node of next level if exist if (remove.right != null ) { queue.Enqueue(remove.right); } } // Assig Value of current Level Sum to Sum // arr sum[currentLevel] = current_LevelSum; // Increasing Level for next Iteration currentLevel++; } } public static void Main( string [] args) { // Creating Tree Node root = newNode(6); root.left = newNode(4); root.right = newNode(8); root.left.left = newNode(3); root.left.right = newNode(5); root.right.left = newNode(7); root.right.right = newNode(9); // Finding How Many Level Does The Tree Have int levels = getHeight(root) + 1; int [] sum = new int [levels]; // Calling The Function calculateLevelSum_Using_BFS(root, sum); // Printing the Array printArr(sum, levels); } // This Code is Contributed By Vikas Bishnoi } |
6 12 24
Time Complexity: O(N) Where is the number of Nodes in a tree. As Each Node is only Visited Once so Complexity is O(N)
Auxiliary Space: O(N) Used In queue to store nodes
Contact Us