Authors:
Stuart Reges, Marty Stepp
Chapter:
Binary Trees
Exercise:
Exercises
Question:4 | ISBN:9780136091813 | Edition: 2
Question
Write a method called depthSum that returns the sum of the values stored in a binary tree of integers weighted by the depth of each value. The method should return the value at the root, plus 2 times the values stored at the next level of the tree, plus 3 times the values stored at the next level of the tree, and so on. For example, the depth sum of reference tree #1 would be computed as
(1 * 3) + (2 * (5 + 2)) + (3 * (1 + 4 + 6)) = 50 .
Add the above method to the IntTree class from this chapter. You may define additional private methods to implement your public method if necessary. Several problem descriptions refer to the following reference binary trees:
Answer
Implementation of depthSum method:
public int depthSum()
{
return depthSum(overallRoot, 1);
}
private int depthSum(IntTreeNode root, int level)
{
if(root == null)
{
return 0;
}
else
{
return level * root.data
+ depthSum(root.left, level + 1)
+ depthSum(root.right, level + 1);
}
}