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&lt;Integer&gt; items) { 
        create(items);
    }


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

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

        final Queue&lt;TreeNode&gt; queue = new LinkedList&lt;TreeNode&gt;();
        queue.add(root);

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

        for (int i = 0; i &lt; 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));
                    queue.add(current.left);
                }
                if (right &lt; items.size() &amp;&amp; items.get(right) != null) {
                    current.right = new TreeNode(items.get(right));
                    queue.add(current.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 &lt;= 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 &lt; 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;
}



really made me wonder. You're threading this object through recursive calls to hold the answer.

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 &lt;= 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 &lt; 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 &lt;= 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 &lt; node.item) {
      node = node.left;
    } else {
      floor = node.item;
      node = node.right;
    }
  }
  return floor;
}