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


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.