Give an algorithm for finding the sum of all elements in a binary tree.
In the above binary tree sum = 106.
The idea is to recursively, call left subtree sum, right subtree sum and add their values to current node’s data.
Implementation:
C++
/* Program to print sum of all the elements of a binary tree */#include <bits/stdc++.h>using namespace std;struct Node { int key; Node* left, *right;};/* utility that allocates a new Node with the given key */Node* newNode(int key){ Node* node = new Node; node->key = key; node->left = node->right = NULL; return (node);}/* Function to find sum of all the elements*/int addBT(Node* root){ if (root == NULL) return 0; return (root->key + addBT(root->left) + addBT(root->right));}/* Driver program to test above functions*/int main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); int sum = addBT(root); cout << "Sum of all the elements is: " << sum << endl; return 0;} |
Java
// Java Program to print sum of// all the elements of a binary treeclass GFG{static class Node { int key; Node left, right; }/* utility that allocates a new Node with the given key */static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return (node); } /* Function to find sum of all the elements*/static int addBT(Node root) { if (root == null) return 0; return (root.key + addBT(root.left) + addBT(root.right)); } // Driver Codepublic static void main(String args[]){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); int sum = addBT(root); System.out.println("Sum of all the elements is: " + sum); } }// This code is contributed by Arnab Kundu |
Python3
# Python3 Program to print sum of all # the elements of a binary tree # Binary Tree Node """ utility that allocates a new Node with the given key """class newNode: # Construct to create a new node def __init__(self, key): self.key = key self.left = None self.right = None # Function to find sum of all the element def addBT(root): if (root == None): return 0 return (root.key + addBT(root.left) + addBT(root.right)) # Driver Code if __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.right.left = newNode(6) root.right.right = newNode(7) root.right.left.right = newNode(8) sum = addBT(root) print("Sum of all the nodes is:", sum)# This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
using System;// C# Program to print sum of // all the elements of a binary tree public class GFG{public class Node{ public int key; public Node left, right;}/* utility that allocates a new Node with the given key */public static Node newNode(int key){ Node node = new Node(); node.key = key; node.left = node.right = null; return (node);}/* Function to find sum of all the elements*/public static int addBT(Node root){ if (root == null) { return 0; } return (root.key + addBT(root.left) + addBT(root.right));}// Driver Code public static void Main(string[] args){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); int sum = addBT(root); Console.WriteLine("Sum of all the elements is: " + sum);}}// This code is contributed by Shrikant13 |
Javascript
<script>// Javascript Program to print sum of// all the elements of a binary treeclass Node { constructor(key) { this.key=key; this.left=this.right=null; }}/* Function to find sum of all the elements*/function addBT(root){ if (root == null) return 0; return (root.key + addBT(root.left) + addBT(root.right)); }// Driver Codelet root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.right.left.right = new Node(8); let sum = addBT(root); document.write("Sum of all the elements is: " + sum); // This code is contributed by avanitrachhadiya2155</script> |
Output
Sum of all the elements is: 36
Time Complexity: O(N)
Auxiliary Space: O(1), but if we consider space due to the recursion call stack then it would be O(h), where h is the height of the Tree.
Method 2 – Another way to solve this problem is by using Level Order Traversal. Every time when a Node is deleted from the queue, add it to the sum variable.
Implementation:
C++
#include <bits/stdc++.h>#include <iostream>using namespace std;struct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}/*Function to find sum of all elements*/int sumBT(Node* root){ //sum variable to track the sum of //all variables. int sum = 0; queue<Node*> q; //Pushing the first level. q.push(root); //Pushing elements at each level from //the tree. while (!q.empty()) { Node* temp = q.front(); q.pop(); //After popping each element from queue //add its data to the sum variable. sum += temp->key; if (temp->left) { q.push(temp->left); } if (temp->right) { q.push(temp->right); } } return sum;}// Driver programint main(){ // Let us create Binary Tree shown in above example Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); cout << "Sum of all elements in the binary tree is: " << sumBT(root);}//This code is contributed by Sarthak Delori |
Java
// Java Program to print sum of// all the elements of a binary treeimport java.util.LinkedList;import java.util.Queue;class GFG { static class Node { int key; Node left, right; } // Utility function to create a new node static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return (node); } /*Function to find sum of all elements*/ static int sumBT(Node root) { // sum variable to track the sum of // all variables. int sum = 0; Queue<Node> q = new LinkedList<Node>(); // Pushing the first level. q.add(root); // Pushing elements at each level from // the tree. while (!q.isEmpty()) { Node temp = q.poll(); // After popping each element from queue // add its data to the sum variable. sum += temp.key; if (temp.left != null) { q.add(temp.left); } if (temp.right != null) { q.add(temp.right); } } return sum; } // Driver Code public static void main(String args[]) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); int sum = sumBT(root); System.out.println( "Sum of all elements in the binary tree is: " + sum); }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
Python3
# Python3 Program to print sum of all# the elements of a binary tree# Binary Tree Nodeclass newNode: # Utility function to create a new node def __init__(self, key): self.key = key self.left = None self.right = None# Function to find sum of all the elementdef sumBT(root): # sum variable to track the sum of # all variables. sum = 0 q = [] # Pushing the first level. q.append(root) # Pushing elements at each level from # the tree. while len(q) > 0: temp = q.pop(0) # After popping each element from queue # add its data to the sum variable. sum += temp.key if (temp.left != None): q.append(temp.left) if temp.right != None: q.append(temp.right) return sum# Driver Codeif __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.right.left = newNode(6) root.right.right = newNode(7) root.right.left.right = newNode(8) print("Sum of all elements in the binary tree is: ", sumBT(root))# This code is contributed by# Abhijeet Kumar(abhijeet19403) |
C#
// C# Program to print sum of// all the elements of a binary treeusing System;using System.Collections.Generic;public class GFG { public class Node { public int key; public Node left, right; } // Utility function to create a new node public static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return (node); } /*Function to find sum of all elements*/ public static int sumBT(Node root) { // sum variable to track the sum of // all variables. int sum = 0; Queue<Node> q = new Queue<Node>(); // Pushing the first level. q.Enqueue(root); // Pushing elements at each level from // the tree. while (q.Count!=0) { Node temp = q.Dequeue(); // After popping each element from queue // add its data to the sum variable. sum += temp.key; if (temp.left != null) { q.Enqueue(temp.left); } if (temp.right != null) { q.Enqueue(temp.right); } } return sum; } // Driver Code public static void Main(string[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); Console.WriteLine("Sum of all elements in the binary tree is: " + sumBT(root)); }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
Javascript
<script>// Javascript Program to print sum of// all the elements of a binary treeclass Node { // Utility function to create a new node constructor(key) { this.key=key; this.left=this.right=null; }}/* Function to find sum of all the elements*/function sumBT(root){ // sum variable to track the sum of // all variables. let sum = 0; let q = []; // Pushing the first level. q.push(root); // Pushing elements at each level from // the tree. while (q.length != 0) { let temp = q.shift(); // After popping each element from queue // add its data to the sum variable. sum += temp.key; if (temp.left != null) { q.add(temp.left); } if (temp.right != null) { q.add(temp.right); } } return sum;}// Driver Codelet root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.right.left.right = new Node(8); document.write("Sum of all elements in the binary tree is: " + sumBT(root)); // This code is contributed by Abhijeet Kumar(abhijeet19403)</script> |
Output
Sum of all elements in the binary tree is: 36
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3: Using Morris traversal:
The Morris Traversal algorithm is an in-order tree traversal algorithm that does not require the use of a stack or recursion, and uses only constant extra memory. The basic idea behind the Morris Traversal algorithm is to use the right child pointers of the nodes to create a temporary link back to the node's parent, so that we can easily traverse the tree without using any extra memory.
Follow the steps below to implement the above idea:
- Initialize a variable sum to 0 to keep track of the sum of all nodes in the binary tree.
- Initialize a pointer root to the root of the binary tree.
- While root is not null, perform the following steps:
If the left child of root is null, add the value of root to sum, and move to the right child of root.
If the left child of root is not null, find the rightmost node of the left subtree of root and create a temporary link back to root.
Move to the left child of root. - After the traversal is complete, return sum.
Below is the implementation of the above approach:
C++
// C++ code to implement the morris traversal approach#include <iostream>using namespace std;// Definition of a binary tree nodestruct Node { int val; Node* left; Node* right; Node(int v) : val(v) , left(nullptr) , right(nullptr) { }};// Morris Traversal function to find the sum of all nodes in// a binary treelong int sumBT(Node* root){ long int sum = 0; while (root != nullptr) { if (root->left == nullptr) { // If there is no left child, add // the value of the current node // to the sum and move to the // right child sum += root->val; root = root->right; } else { // If there is a left child Node* prev = root->left; while ( prev->right != nullptr && prev->right != root) // Find the rightmost node // in the left subtree of // the current node prev = prev->right; if (prev->right == nullptr) { // If the right child of the // rightmost node is null, set // it to the current node and // move to the left child prev->right = root; root = root->left; } else { // If the right child of the rightmost // node is the current node, set it to // null, add the value of the current // node to the sum and move to the right // child prev->right = nullptr; sum += root->val; root = root->right; } } } return sum;}// Driver codeint main(){ // Example binary tree: 1 // / \ // 2 3 // / \ // 4 5 Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); // Find the sum of all nodes in the binary tree long int sum = sumBT(root); cout << "Sum of all nodes in the binary tree is " << sum << endl; return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
// Java code to implement the Morris traversal approachclass Node { int val; Node left, right; Node(int item) { val = item; left = right = null; }}class GFG { // Function to find the sum of all nodes in a binary tree static long sumBT(Node root) { long sum = 0; while (root != null) { if (root.left == null) { // If there is no left child, add // the value of the current node // to the sum and move to the // right child sum += root.val; root = root.right; } else { // If there is a left child Node prev = root.left; while (prev.right != null && prev.right != root) // Find the rightmost node // in the left subtree of // the current node prev = prev.right; if (prev.right == null) { // If the right child of the // rightmost node is null, set // it to the current node and // move to the left child prev.right = root; root = root.left; } else { // If the right child of the rightmost // node is the current node, set it to // null, add the value of the current // node to the sum and move to the right // child prev.right = null; sum += root.val; root = root.right; } } } return sum; } // Driver code public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); // Find the sum of all nodes in the binary tree long sum = sumBT(root); System.out.println("Sum of all nodes in the binary tree is : " + sum); }}//This code is contributed by Veerendra_Singh_Rajpoot |
Python3
# Definition of a binary tree nodeclass Node: def __init__(self, v): self.val = v self.left = None self.right = None# Morris Traversal function to find the sum of all nodes in# a binary treedef sumBT(root): sum = 0 while root: if root.left is None: # If there is no left child, add the value of the # current node to the sum and move to the right child sum += root.val root = root.right else: # If there is a left child prev = root.left while prev.right and prev.right != root: # Find the rightmost node in the left subtree # of the current node prev = prev.right if prev.right is None: # If the right child of the rightmost node is null, # set it to the current node and move to the left child prev.right = root root = root.left else: # If the right child of the rightmost node is the # current node, set it to null, add the value of # the current node to the sum and move to the right child prev.right = None sum += root.val root = root.right return sum# Driver codeif __name__ == "__main__": # Example binary tree: 1 # / \ # 2 3 # / \ # 4 5 root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) # Find the sum of all nodes in the binary tree sum = sumBT(root) print("Sum of all nodes in the binary tree is", sum) |
C#
using System;// Definition of a binary tree nodepublic class Node{ public int val; public Node left; public Node right; public Node(int v) { val = v; left = null; right = null; }}public class MorrisTraversal{ // Morris Traversal function to find the sum of all nodes in // a binary tree public static long SumBT(Node root) { long sum = 0; while (root != null) { if (root.left == null) { // If there is no left child, add // the value of the current node // to the sum and move to the // right child sum += root.val; root = root.right; } else {// If there is a left child Node prev = root.left; // Find the rightmost node // in the left subtree of // the current node while (prev.right != null && prev.right != root) { prev = prev.right; } // If the right child of the // rightmost node is null, set // it to the current node and // move to the left child if (prev.right == null) { prev.right = root; root = root.left; } // If the right child of the rightmost // node is the current node, set it to // null, add the value of the current // node to the sum and move to the right // child else { prev.right = null; sum += root.val; root = root.right; } } } return sum; } // Driver code public static void Main(string[] args) { // Example binary tree: 1 // / \ // 2 3 // / \ // 4 5 Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); // Find the sum of all nodes in the binary tree long sum = SumBT(root); Console.WriteLine("Sum of all nodes in the binary tree is " + sum); // Clean up memory (optional) root = null; // Prevent the console window from closing immediately Console.ReadLine(); }}// This code is contributed by rambabuguphka |
Javascript
// Definition of a binary tree nodeclass TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}// Morris Traversal function to find the sum of all nodes in a binary treefunction sumBT(root) { let sum = 0; while (root !== null) { if (root.left === null) { // If there is no left child, add the value of the current node to the sum // and move to the right child sum += root.val; root = root.right; } else { // If there is a left child let prev = root.left; while (prev.right !== null && prev.right !== root) { // Find the rightmost node in the left subtree of the current node prev = prev.right; } if (prev.right === null) { // If the right child of the rightmost node is null, set it to the current node // and move to the left child prev.right = root; root = root.left; } else { // If the right child of the rightmost node is the current node, // set it to null, add the value of the current node to the sum, // and move to the right child prev.right = null; sum += root.val; root = root.right; } } } return sum;}// Driver codefunction main() { // Example binary tree: 1 // / \ // 2 3 // / \ // 4 5 const root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); // Find the sum of all nodes in the binary tree const sum = sumBT(root); console.log("Sum of all nodes in the binary tree is " + sum);}// Call the main function to start the programmain(); |
Output
Sum of all nodes in the binary tree is 15
Time Complexity: O(n) , Because of all the nodes are traversing only once.
Auxiliary Space: O(1)
This article is contributed by Prakriti Gupta. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
