logo
  • Home
  • Test & Rank
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Mining
  • Marine
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Jobs
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

C Program to Find the Sum of All Nodes in a Binary Tree

Posted on June 21, 2013 by Manish

This is a C Program to find the sum of all the nodes present in a Binary Tree using recursion.

Problem Description

We have to write a C program which will find the sum of all the nodes in a Binary Tree.

Expected Input and Output

Case 1. Balanced Tree:When the weight is equal on both the sides of root.

advertisement
                    25
                  /    \  
                 27     19   
                / \     / \ 
              17  91   13 55

Output: 247

Case 2. Right Skewed Tree:When the nodes at every level just have a right child.

                    1   
                     \
                      2    
                       \    
                        3 
                         \
                          4
                           \
                            5

Output: 15

advertisement

Case 3. Tree having just one node

                    15

Output: 15

Problem Solution

There are two ways we can find the sum of all the nodes in a given Binary Tree.
Approach One

We can store the elements of tree in an array by using any of the traversal    techniques and then find the sum of the array elements.

Approach Two

We keep on adding the values of nodes as we traverse them. We do this till we  traverse the whole tree.

Here in this program we will be using second approach because if we use first approach we will have to create an array which will take up some space. We can avoid this by using second approach.

advertisement
Program/Source Code

Here is source code of the C Program for finding the sum of all the nodes in a binary tree. The program is successfully compiled and tested using Codeblocks gnu/GCC compiler on windows 10. The program output is also shown below.

  1. /* C Program for finding the sum of all the nodes in a Tree */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. struct node
  5. {
  6.     int info;
  7.     struct node *left, *right;
  8. };
  9. struct node *createnode(int key)
  10. {
  11.     struct node *newnode = (struct node*)malloc(sizeof(struct node));
  12.     newnode->info = key;
  13.     newnode->left = NULL;
  14.     newnode->right = NULL;
  15.     return(newnode);
  16. }
  17. int sumofnodes(struct node *root)
  18. {
  19.     int rightsubtree, leftsubtree, sum = 0;
  20.     if(root != NULL)
  21.     {
  22.         leftsubtree = sumofnodes(root->left);
  23.         rightsubtree = sumofnodes(root->right);
  24.         sum = (root->info) + leftsubtree + rightsubtree;
  25.         return sum;
  26.     }
  27. }
  28. /*
  29.  * Main Function
  30.  */
  31. int main()
  32. {
  33.    /* Creating first Tree. */
  34.     struct node *newnode = createnode(25);
  35.     newnode->left = createnode(27);
  36.     newnode->right = createnode(19);
  37.     newnode->left->left = createnode(17);
  38.     newnode->left->right = createnode(91);
  39.     newnode->right->left = createnode(13);
  40.     newnode->right->right = createnode(55);
  41.     /* Sample Tree 1:
  42.      *                25
  43.      *             /    \
  44.      *            27     19
  45.      *           / \     / \
  46.      *         17  91   13 55
  47.      */
  48.     printf("Sum of nodes in tree 1 = %d", sumofnodes(newnode));
  49.     printf("\n");
  50.  
  51.     /* Creating second Tree. */
  52.     struct node *node = createnode(1);
  53.     node->right = createnode(2);
  54.     node->right->right = createnode(3);
  55.     node->right->right->right = createnode(4);
  56.     node->right->right->right->right = createnode(5);
  57.     /* Sample Tree 2:   Right Skewed Tree (Unbalanced).
  58.      *               1
  59.      *                \
  60.      *                 2
  61.      *                  \
  62.      *                   3
  63.      *                    \
  64.      *                     4
  65.      *                      \
  66.      *                       5
  67.      */
  68.     printf("Sum of nodes in tree 2 = %d", sumofnodes(node));
  69.     printf("\n");
  70.  
  71.     /* Creating third Tree. */
  72.     struct node *root = createnode(15);
  73.     /* Sample Tree 3: Tree having just one root node.
  74.      *              15
  75.      */
  76.     printf("Sum of nodes in tree 3 = %d", sumofnodes(root));
  77.     printf("\n");
  78.     return 0;
  79. }
Program Explanation

Program contains two important functions.

1. createnode(key);
This function helps to create a new node by allocating it a memory dynamically. It has just one parameter which is “key” which assigns value to the node thereby creating a fresh node having left and right child as “NULL”.

2. sumofnodes(struct node *root);
In this function we have passed root node of a tree as a parameter and traversed each node of the tree. We have first traversed and added the values(info) of nodes in left subtree and stored it in sum variable then we have traversed the right subtree and added the values(info) of the nodes. Once we traverse the whole tree and add the values of all the nodes we return the value contained in variable “sum”.

Runtime Test Cases
Sum of nodes in tree 1 = 247
Sum of nodes in tree 2 = 15
Sum of nodes in tree 3 = 15

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Reference Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.
« Prev Page - C Program to Reverse the String using Both Recursion and Iteration
» Next Page - C Program to Display Every Possible Combination of Two Words from the given 2 String without Displaying Repeated Combinations

« C Program to Reverse the String using Both Recursion and Iteration
C Program to Display Every Possible Combination of Two Words from the given 2 String without Displaying Repeated Combinations »
advertisement

Deep Dive @ Sanfoundry:

  1. C++ Programming Examples on Data-Structures
  2. C Programming Examples on Data-Structures
  3. C# Programming Examples on Data Structures
  4. C Programming Examples using Recursion
  5. Python Programming Examples on Graphs
  6. C Programming Examples on Linked List
  7. C Programming Examples without using Recursion
  8. Python Programming Examples on Linked Lists
  9. Python Programming Examples on Trees
  10. C Programming Examples on Trees
Manish Bhojasia
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Facebook | Twitter

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.