JAVA Recursively complete the sizeBelowMethod for a binary tree. This should ret
ID: 3875997 • Letter: J
Question
JAVA Recursively complete the sizeBelowMethod for a binary tree. This should return all the total of all nodes below depth of k. One helper function must be used.
public class MyIntSET {
private Node root;
private static class Node {
public final int key;
public Node left, right;
public Node(int key) { this.key = key; }
}
// the number of nodes in the tree, "below" depth k (not including k)
// include node n if depth(n) > k
public int sizeBelowDepth(int k) {
// TODO
return 0;
}
Explanation / Answer
Below is your code: -
public class MyIntSET {
private Node root;
private static class Node {
public final int key;
public Node left, right;
public Node(int key) { this.key = key; }
}
// the number of nodes in the tree, "below" depth k (not including k)
// include node n if depth(n) > k
public int sizeBelowDepth(int k) {
return sizeBelowDepthHelper(root,0,k);
}
public static int sizeBelowDepthHelper(Node t, int depth, final int k) {
if (t == null) {
return 0;
}
int below = sizeBelowDepthHelper(t.left, depth+1, k) +
sizeBelowDepthHelper(t.right, depth+1, k);
if (depth > k){
below++;
}
return below;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.