# Find floor and ceiling in the BST

Find ceiling and floor in the BinarySearchTree. Looking for code-review, optmizations and best practices.

public class FloorCeiling {

private TreeNode root;

public FloorCeiling(List<Integer> items) {
create(items);
}

private void create (List<Integer> items) {
if (items.isEmpty())  {
throw new NullPointerException("The items array is empty.");
}

root = new TreeNode(items.get(0));

final Queue<TreeNode> queue = new LinkedList<TreeNode>();

final int half = items.size() / 2;

for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;

if (items.get(left) != null) {
current.left = new TreeNode(items.get(left));
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode(items.get(right));
}
}
}
}

private static class TreeNode {
private TreeNode left;
private int item;
private TreeNode right;

TreeNode(int item) {
this.item = item;
}
}

private static class IntegerObj {
Integer obj = null;
}

public int ceiling (int val) {
IntegerObj iobj = new IntegerObj();
recurseCeiling(root, iobj, val);
return iobj.obj;
}

public int floor (int val) {
IntegerObj iobj = new IntegerObj();
recurseFloor(root, iobj, val);
return iobj.obj;
}

private void recurseCeiling (TreeNode node,  IntegerObj iobj, int value) {
if (node == null) {
return;
}
if (value <= node.item) {
iobj.obj = node.item;
recurseCeiling(node.left, iobj, value);
} else {
recurseCeiling(node.right, iobj, value);
}
}

private void recurseFloor (TreeNode node, IntegerObj iobj, int value) {
if (node == null) {
return;
}
if (value < node.item) {
recurseFloor (node.left, iobj, value);
} else {
iobj.obj = node.item;
recurseFloor (node.right, iobj, value);
}
}
}

public class FloorCeilingTest {

@Test
public void test1() {
FloorCeiling fc1 = new FloorCeiling(Arrays.asList(100, 50, 150, 25, 75, 125, 175));
assertEquals(25,  fc1.ceiling(20));
assertEquals(50,  fc1.ceiling(30));
assertEquals(75,  fc1.ceiling(70));
assertEquals(100, fc1.ceiling(90));
assertEquals(125, fc1.ceiling(120));
assertEquals(150, fc1.ceiling(145));
assertEquals(175, fc1.ceiling(160));
}

@Test
public void test2() {
FloorCeiling fc2 = new FloorCeiling(Arrays.asList(100, 50, 150, 25, 75, 125, 175));
assertEquals(25,  fc2.floor(27));
assertEquals(50,  fc2.floor(55));
assertEquals(75,  fc2.floor(78));
assertEquals(100, fc2.floor(110));
assertEquals(125, fc2.floor(128));
assertEquals(150, fc2.floor(160));
assertEquals(175, fc2.floor(180));
}

}

-

This:

private static class IntegerObj {
Integer obj = null;
}


Instead you can remove this class and change your methods to return an int:

public int ceiling(int val) {
return recurseCeiling(root, null, val);
}

public int floor(int val) {
return recurseFloor(root, null, val);
}

private int recurseCeiling(TreeNode node, Integer ceil, int value) {
if (node == null) {
return ceil;
}
if (value <= node.item) {
return recurseCeiling(node.left, node.item, value);
}
return recurseCeiling(node.right, ceil, value);
}

private int recurseFloor(TreeNode node, Integer floor, int value) {
if (node == null) {
return floor;
}
if (value < node.item) {
return recurseFloor(node.left, floor, value);
}
return recurseFloor(node.right, node.item, value);
}


We can now see that these methods can be written iteratively

private int recurseCeiling(TreeNode node, Integer ceil, int value) {
while (node != null) {
if (value <= node.item) {
ceil = node.item;
node = node.left;
} else {
node = node.right;
}
}
return ceil;
}

private int recurseFloor(TreeNode node, Integer floor, int value) {
while (node != null) {
if (value < node.item) {
node = node.left;
} else {
floor = node.item;
node = node.right;
}
}
return floor;
}

-

### Unit testing

Your unit tests are poorly named and tedious. This would be better:

@Test
public void testCeiling() {
List<Integer> list = Arrays.asList(100, 50, 150, 25, 75, 125, 175);
FloorCeiling fc1 = new FloorCeiling(list);
for (int item : list) {
assertEquals(item, fc1.ceiling(item));
assertEquals(item, fc1.ceiling(item - 1));
}
}

@Test
public void testFloor() {
List<Integer> list = Arrays.asList(100, 50, 150, 25, 75, 125, 175);
FloorCeiling fc1 = new FloorCeiling(list);
for (Integer item : list) {
assertEquals(item, fc1.floor(item));
assertEquals(item, fc1.floor(item + 1));
}
}


### What if there's no ceiling / floor?

If there's no ceiling / floor the methods will crash with an NPE. It might be nice to throw NoSuchElementException instead:

public int ceiling(int val) {
Integer ceil = recurseCeiling(root, null, val);
if (ceil != null) {
return ceil;
}
throw new NoSuchElementException("No ceiling for " + val);
}

// building on @mjolka's solution
private Integer recurseCeiling(TreeNode node, Integer ceil, int value) {
if (node == null) {
return ceil;
}
if (value <= node.item) {
return recurseCeiling(node.left, node.item, value);
}
return recurseCeiling(node.right, ceil, value);
}

@Test(expected = NoSuchElementException.class)
public void testNoCeiling() {
List<Integer> list = Arrays.asList(100, 50, 150, 25, 75, 125, 175);
FloorCeiling fc1 = new FloorCeiling(list);
fc1.ceiling(Collections.max(list) + 1);
}

-

How do you define "floor" and "ceiling"? By analogy to $\lfloor 3 \rfloor = 3$ and $\lceil 3 \rceil = 3$, I would expect that if the tree happens to contain a node that is exactly n, then floor(n) and ceiling(n) would return n. Instead, you keep recursing. The unit tests should have included a test case for that.

You added some unnecessary complications that were rather puzzling. In particular, IntegerObj seems to serve no useful purpose. It looks like it might have been intended as a kind of mutable version of Integer. However, you could have just used a TreeNode for that purpose. Furthermore, you don't need any kind of mutation ability at all: it's a straightforward recursion problem.

public int ceiling(int limit) {
return recurseCeiling(root, root.item, limit);
}

private int recurseCeiling(TreeNode node, int tentativeResult, int limit) {
return (node == null || limit == node.item) ? tentativeResult :
(limit < node.item) ? recurseCeiling(node.left, node.item, limit)
: recurseCeiling(node.right, tentativeResult, limit);
}

-