roblem 3: Create a program named TreeweightedSum.java and implement the followin
ID: 3711635 • Letter: R
Question
roblem 3: Create a program named TreeweightedSum.java and implement the following method: public int weightedSum (BT bt) This method accepts a BT as a parameter and returns the sum of the values stored in a binary tree of integers weighted by the depth of each value. You 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 plus 4 times the values stored at the next level of the tree and so on. For example, in the tree below: 10 4. 20 6 25 The sum would be computed as: 1 * 9 2 * (5 + 10) + 3 * (4 7 20) + 4 * (6 + 25)256Explanation / Answer
public class TreeWeightedSum {
public int weightedSum(BT bt) {
int sum = 0;
if(bt.root != null) {
sum += weightedSumHelper(bt.root, 1);
}
return sum;
}
/**
* Helper function to get weighted sum. Goes layer by layer
* @param node
* @param level of the node
* @return weighted sum of the tree with root = node
*/
private int weightedSumHelper(BTNode node, int level) {
if(node == null) return 0;
else {
// Return sum of weighted sum of left child, right child and self
return level * node.getData() +
weightedSumHelper(node.getLeft(), level + 1) +
weightedSumHelper(node.getRight(), level + 1);
}
}
}
==============================================================
public class BTTest {
public static void main(String [] args) {
BT bt = new BT();
bt.insertNode(9);
bt.insertNode(5);
bt.insertNode(10);
bt.insertNode(4);
bt.insertNode(7);
bt.insertNode(20);
bt.insertNode(6);
bt.insertNode(25);
System.out.println(new TreeWeightedSum().weightedSum(bt));
}
}
=========================================
public class BTNode {
private BTNode left, right;
private int data;
public BTNode() {
left = right = null;
data = 0;
}
public BTNode(int data) {
this.data = data;
left = right = null;
}
public void setLeft(BTNode node) {
left = node;
}
public void setRight(BTNode node) {
right = node;
}
public BTNode getLeft() {
return left;
}
public BTNode getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}
public int compareTo(BTNode node) {
return data - node.data;
}
public int compareTo(int data) {
return this.data - data;
}
}
========================================
public class BT {
BTNode root;
public BT() {
root = null;
}
public void insertNode(int data) {
insertNode(new BTNode(data));
}
public void insertNode(BTNode node) {
root = insertNodeHelper(root, node);
}
private BTNode insertNodeHelper(BTNode tree, BTNode node) {
if (tree == null)
tree = node;
else if (node.compareTo(tree) <= 0)
tree.setLeft(insertNodeHelper(tree.getLeft(), node));
else
tree.setRight(insertNodeHelper(tree.getRight(), node));
return tree;
}
}
================================================================
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.