Sum of all the nodes in a tree

Given a binary tree, where each node is having an integer value.

Write a function that accept the root of this tree and returns the sum of all the nodes in the tree. The sum of all the nodes in the following tree is 32

Solution:

Like other Binary tree questions, this one also use recursion. The signature of our function is:

int sumOfNodes(Node* root);

This function computes the sum of all the node of the binary tree pointer to by root and return that sum. The function can be defined recursively:

Sum of all nodes = Sum of all nodes in left subtree + sum of all nodes in right subtree + data at root

Now we just need to put the terminating condition to this recursion and the final code of function looks like below:

int sumOfNodes(Node* root)
{
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        return sumOfNodes(root->left) + sumOfNodes(root->right) + root->data;
    }
}

Above implementation is in C++. Below is the sample code in Java with such a function

// DEFINITION OF NODE OF A BINARY TREE
class Node
{
    public int data;
    public Node left;
    public Node right;
    public Node(int x){
        data = x;
        left = right= null;
    }
}
// CLASS BINARY TREE. THERE CAN BE MULTIPLE FUNCTION IN THIS CLASS
class BinaryTree
{
    Node root;
    BinaryTree(){
        root= null;
    }
    //Main function that computes the sum of function
    private int sumOfNodes(Node r)
    {
        if(r == null){ return 0; }
        return r.data + sumOfNodes(r.left) + sumOfNodes(r.right);
    }
    // WRAPPER FUNCTION TO CALL THE ABOVE RECURSIVE FUNCTION
    public int sumOfNodes()
    {
        return sumOfNodes(root);
    }
    // FUNCTION TO CREATE A TREE WITH SAMPLE NODES
    void populateNodes()
    {
        root = new Node(6);
        root.left = new Node(3);
        root.right = new Node(1);
        root.left.left = new Node(4);
        root.right.left = new Node(5);
        root.right.right = new Node(10);
        root.right.left.right = new Node(3);
    }
}
// CLASS WITH main FUNCTION
class RTDemo
{
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.populateNodes();
        System.out.println(tree.sumOfNodes());
    }
}

The function sumOfNodes takes O(n) time.