Given a binary tree and a positive integer \$k\$, print all nodes that are distance \$k\$ from a leaf node.
Here, the meaning of distance is different from the previous post. Here, \$k\$ is the distance from a leaf means \$k\$ levels higher than a leaf node. For example, if \$k\$ is more than height of binary tree, then nothing should be printed. Expected time complexity is \$O(n)\$ where \$n\$ is the number nodes in the given binary tree.
I'm looking for code review, optimizations and best practices. I'm verifying \$O(n)\$ to be both the time and space complexity.
public class KDistanceFromLeaves<T> {
private TreeNode<T> root;
public KDistanceFromLeaves(List<T> items) {
create(items);
}
private void create (List<T> items) {
root = new TreeNode<T>(items.get(0));
final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode<T> current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode<T>(items.get(left));
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<T>(items.get(right));
queue.add(current.right);
}
}
}
}
public static class TreeNode<T> {
private TreeNode<T> left;
private T item;
private TreeNode<T> right;
TreeNode(T item) {
this.item = item;
}
}
public List<T> kDistanceFromLeaf(int k) {
final List<T> list = new ArrayList<>();
final List<Boolean> booleanList = new ArrayList<>();
recurse(root, k, new ArrayList<T>(), list, booleanList);
return list;
}
private void recurse(TreeNode<T> node, int k, List<T> items, List<T> list, List<Boolean> visited) {
if (node == null) return;
if (node.left == null && node.right == null && k <= items.size() && !visited.get(items.size() - k)) {
list.add(items.get(items.size() - k));
visited.set(items.size() - k, true);
}
items.add(node.item);
visited.add(false);
recurse(node.left, k, items, list, visited);
recurse(node.right, k, items, list, visited);
items.remove(items.size() - 1);
visited.remove(visited.size() - 1);
}
}
public class KDistanceFromLeavesTest {
@Test
public void testCompleteTree() {
KDistanceFromLeaves<Integer> kd = new KDistanceFromLeaves<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
assertEquals(Arrays.asList(2, 3), kd.kDistanceFromLeaf(1));
assertEquals(Arrays.asList(1), kd.kDistanceFromLeaf(2));
assertEquals(Collections.EMPTY_LIST, kd.kDistanceFromLeaf(3));
assertEquals(Collections.EMPTY_LIST, kd.kDistanceFromLeaf(4));
}
@Test
public void testInCompleteTree() {
KDistanceFromLeaves<Integer> kd1 = new KDistanceFromLeaves<Integer>(Arrays.asList(1, 2, 3, 4, 5, null, null, null, null, 6, 7));
assertEquals(Arrays.asList(2, 5, 1), kd1.kDistanceFromLeaf(1));
assertEquals(Arrays.asList(1, 2), kd1.kDistanceFromLeaf(2));
assertEquals(Arrays.asList(1), kd1.kDistanceFromLeaf(3));
assertEquals(Collections.EMPTY_LIST, kd1.kDistanceFromLeaf(4));
}
}
