CODEWITHSUNDEEP
javarecursionbinary-tree
Pat K
Pat K

Reputation: 321

Sum values in binary tree of integers weighted by depth

Here is my reference tree:

    3
   / \
  5   2
 /   / \
1   4   6

Here is the expected output of the recursive method:

(1*3) + (2 * (5 + 2)) + (3 * (1 + 4 + 6)) = 50

...and here is the code I have thus far:

public int depthSum()
{
    int depth = 1;
    return depthSum(overallRoot, depth);
}

public int depthSum(IntTreeNode someNode, int someDepth)
{
    if(someNode == null)
    {
        return 0;
    }
    else
    {
        return someDepth * someNode.data + //some recursion
    }
}

I get that I have to likely call myself and increment someDepth, but I can't seem to get this right. Any ideas?

Upvotes: 1

Views: 2827

Answers (1)

paddy
paddy

Reputation: 63451

Presumably you mean:

return someDepth * someNode.data +
       depthSum(someNode.left, someDepth+1) +
       depthSum(someNode.right, someDepth+1);

Upvotes: 4

Related Questions