Find sum of all elements of binary tree in Java - Iterative and recursive

Topics covered

1. Sum of nodes of binary tree -Iterative
2. Sum of nodes of binary tree -Recursive
3. Complete sample program

Problem Statement :- Find sum of all nodes of binary tree.

Sum of nodes of binary tree :-  351

Sum of nodes of binary tree - Iterative
Algorithm : Traverse binary tree in level order traversal and sum all nodes of tree.
Time and space complexity:- TC = O(n) and SC = O(n), n is number of nodes of binary tree.
Sample code for finding diameter of binary tree - time complexity O(n^2),

public int iterativeleveSumOfBinaryTreeNodes(Node root) {
 /* java.util.ArrayDeque */
 Queue<Node> queue = new ArrayDeque<>();
 int sum = 0;
 if (root != null) {
  queue.add(root);
  while (!queue.isEmpty()) {
   /* Dequeue form queue and update sum */
   root = queue.remove();
   sum += root.data;
   Node lc = root.leftChild;
   Node rc = root.rightChild;
   if (lc != null) {
    queue.add(lc);
   }
   if (rc != null) {
    queue.add(rc);
   }
  }
 }
 return sum;
}

Sum of nodes of binary tree - Recursive
Algorithm :- Do recursive preorder traversal and add all nodes in static variable.
1. Make recursive call to find height and diameter of left and right subtree
Sample program for find diameter of binary tree - time complexity O(n)

/* preOrder traversal - sum of all nodes */ public void sumOfAllNodesRecursive(Node root) { if (root == null) return; sumRec += root.data; /* Append node data in string buffer */ sumOfAllNodesRecursive(root.getLeftChild()); sumOfAllNodesRecursive(root.getRightChild()); }

Complete sample program- find diameter of binary tree

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.Queue;

public class SumOfAllNodesOfBinaryTree {
 static int sumRec = 0;

 public int iterativeleveSumOfBinaryTreeNodes(Node root) {
  /* java.util.ArrayDeque */
  Queue<Node> queue = new ArrayDeque<>();
  int sum = 0;
  if (root != null) {
   queue.add(root);
   while (!queue.isEmpty()) {
    /* Dequeue form queue and update sum */
    root = queue.remove();
    sum += root.data;
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
   }
  }
  return sum;
 }

 /* preOrder traversal - sum of all nodes */
 public void sumOfAllNodesRecursive(Node root) {
  if (root == null)
   return;
  sumRec += root.data;
  /* Append node data in string buffer */
  sumOfAllNodesRecursive(root.getLeftChild());
  sumOfAllNodesRecursive(root.getRightChild());
 }

 public static void main(String[] args) {
  SumOfAllNodesOfBinaryTree slo = new SumOfAllNodesOfBinaryTree();
  Node root = slo.new BinaryTree().createTree();
  System.out
    .print("Sum of all nodes of binary" + " tree is(Iterative): ");
  System.out.println(slo.iterativeleveSumOfBinaryTreeNodes(root));
  slo.sumOfAllNodesRecursive(root);
  System.out.print("Sum of all nodes of binary " + "tree is(Recursive): "
    + sumRec);
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));

   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   return root;
  }
 }

 class Node {

  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }
}

===========Sample output===========
Sum of all nodes of binary tree is(Iterative): 351
Sum of all nodes of binary tree is(Recursive): 351
==================================

Related question:-
1. Display sum of nodes of at all level- level by level sum calculation.