In this post, We will learn How to write a Java program to find the sum of all elements in Binary Tree?
For Example, the Sum of all elements in Binary Tree of below Image :
1+2+3+4+5+6+7 = 28
Recursive Approach:
We call recursively, left subtree sum, right subtree sum, and add their values to the current note’s value.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
/** * Function to find the sum of all * elements in Binary Tree using Recursive * approach * @param root * @return sum of elements */ //Note: This Method is written to handle only int data type public int findSumOfAllElementsInBinaryTree(Node<Integer> root) { if(root == null) return 0; return root.data+ findSumOfAllElementsInBinaryTree(root.left)+findSumOfAllElementsInBinaryTree(root.right); } |
Time Complexity : O(n) , Space Complexity : O(n) for recusive Stack
Iterative Approach:
We can use level order traversal with a simple change. Every time after deleting an element from Queue, add the note’s value to sum variable.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * Function to find the sum of all * elements in Binary Tree using Iterative * approach * @param root * @return sum of elements */ //Note: This Method is written to handle only int data type public int findSumOfAllElementsInBinaryTreeItertaiveApproach(Node<Integer> root) { int sum = 0; if(root == null) return sum; Queue<Node<Integer>> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { Node<Integer> temp = queue.poll(); sum += temp.data; if(temp.left != null) queue.offer(temp.left); if(temp.right != null) queue.offer(temp.right); } return sum; } |
Time Complexity : O(n) , Space Complexity : O(n)
Below is the Complete Source code:
BinaryTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
package com.kkjavatutorials.tree; import java.util.LinkedList; import java.util.Queue; public class BinaryTree<E extends Comparable<? super E>> { /** * This internal class represents Node of Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Function to find the sum of all * elements in Binary Tree using Recursive * approach * @param root * @return sum of elements */ //Note: This Method is written to handle only int data type public int findSumOfAllElementsInBinaryTree(Node<Integer> root) { if(root == null) return 0; return root.data+ findSumOfAllElementsInBinaryTree(root.left)+findSumOfAllElementsInBinaryTree(root.right); } /** * Function to find the sum of all * elements in Binary Tree using Iterative * approach * @param root * @return sum of elements */ //Note: This Method is written to handle only int data type public int findSumOfAllElementsInBinaryTreeItertaiveApproach(Node<Integer> root) { int sum = 0; if(root == null) return sum; Queue<Node<Integer>> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { Node<Integer> temp = queue.poll(); sum += temp.data; if(temp.left != null) queue.offer(temp.left); if(temp.right != null) queue.offer(temp.right); } return sum; } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
package com.kkjavatutorials.client; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to find the sum of * all elements in Binary Tree * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Root Node Node<Integer> root = new Node<Integer>(1); Node<Integer> secondNode = new Node<Integer>(2); Node<Integer> thirdNode = new Node<Integer>(3); Node<Integer> fourthNode = new Node<Integer>(4); Node<Integer> fifthNode = new Node<Integer>(5); Node<Integer> sixthNode = new Node<Integer>(6); Node<Integer> seventhNode = new Node<Integer>(7); //Setting Left and right of root Node root.left = secondNode; root.right = thirdNode; root.left.left = fourthNode; root.left.right = fifthNode; root.right.left = sixthNode; root.right.right = seventhNode; //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); System.out.println("Calling the Recursive Method..."); System.out.println("Sum of All Elements:"+binaryTree.findSumOfAllElementsInBinaryTree(root)); System.out.println("Calling the Iterative Method..."); System.out.println("Sum of All Elements:"+binaryTree.findSumOfAllElementsInBinaryTreeItertaiveApproach(root)); } } |
The output of This Program:
Calling the Recursive Method…
Sum of All Elements:28
Calling the Iterative Method…
Sum of All Elements:28
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Difference between binary and binary search trees
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Search operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
Find the node with minimum and maximum values in a Binary Search Tree
Find a mirror image of a binary tree
How do you find if two given binary trees are the same or identical
That’s all about How to write a Java program to find the sum of all elements in Binary Tree?
If you have any feedback or suggestion please feel free to drop in below comment box.