Sum of all nodes in Binary Tree code in c++.

In a Binary Tree, our aim is to find the sum of all nodes in the Binary tree.

The sum of all node can be found using any traversal.H ere we will be using pre-order Traversal for the same.

We just need to traverse the tree and maintain a sum value and keep adding each time a new value is found.

This example is a just simple extension of traversal. We will be using pre-order for implementation. However, you can try different methods also. For any doubts on Pre-order Traversal, you can refer here.

https://prepinsta.com/java-program/depth-first-traversals/

The time complexity for this in O(n)

Readers are suggested to try the iterative version of this program using level order traversal and submit the codes in the comment section below.

 

Code

[code language=”cpp”]

#include<bits/stdc++.h>

struct Treenode// definition of structure of tree node which has lchild child and rchild child
{
int val;
Treenode* lchild;
Treenode* rchild;
};

struct Treenode* newNode(int key)// function for new node creation
{ /* dynamically allocate memory for a new node */
struct Treenode* newnode = (struct Treenode*)malloc(sizeof(struct Treenode));
newnode->val = key;
newnode->lchild = NULL;
newnode->rchild = NULL;

return(newnode);
}
/*
This function returns a binary tree which
satisfy children sum property */
int FindSumNodes(Node* root)
{
if (root == NULL)
return 0;
return (root->val + FindSumNodes(root->lchild) + FindSumNodes(root->rchild));
}

int main()
{
Treenode *root1 = newNode(232);
Treenode *root2 = newNode(232);// these part is concerned with creation of tree
// user can edit this as per wish
root1->lchild = newNode(231);
root1->rchild = newNode(231);
root1->lchild->lchild = newNode(431);
root1->lchild->rchild = newNode(531);

root2->lchild = newNode(231);
root2->rchild = newNode(331);
root2->lchild->lchild = newNode(431);
root2->lchild->rchild = newNode(513);

cout<<FindSumNodes(root)<<endl;

getchar();
return 0;
}

[/code]