Convert sorted linkedlist into balanced binary search tree

Question

Convert a sorted linkedlist into a balanced binary search tree. Looking for code-review, optimizations, and best practices.

public class SortedLinkedListToBalancedBST<T> {

    private TreeNode<T> root;

    private static class TreeNode<T> {
        TreeNode<T> left;
        T item;
        TreeNode<T> right;
    };

    public void convert(LinkedList<T> ll) {
        Iterator<T> itr = ll.iterator();
        root = inorder(0, ll.size() - 1, itr);
    }

    private TreeNode<T> inorder(int lb, int hb, Iterator<T> itr) {
        if (lb > hb) return null;
        // same as (lb+hb)/2, avoids overflow
        int mid = lb + (hb - lb) / 2;

        final TreeNode<T> treeNode = new TreeNode<T>();
        treeNode.left = inorder(lb, mid - 1, itr);
        treeNode.item = itr.next();
        treeNode.right = inorder(mid + 1, hb, itr);

        return treeNode;
    }

    public List<T> getInorderList() {
        final List<T> inorderList = new ArrayList<T>();
        inorder(root, inorderList);
        return inorderList;
    }


    private void inorder(TreeNode<T> node, List<T> list) {
        if (node != null) {
            inorder(node.left,  list);
            list.add(node.item);
            inorder(node.right, list);
        }
    }
}


public class SortedLinkedListToBalancedBSTTest {

    @Test
    public void testOne() {
        SortedLinkedListToBalancedBST<Integer> s = new SortedLinkedListToBalancedBST<Integer>();
        LinkedList<Integer> list1 = new LinkedList<Integer>(Arrays.asList(1, 2, 3, 4));
        s.convert(list1);
        assertEquals(list1,  s.getInorderList());
    }

    @Test
    public void testTwo() {
        SortedLinkedListToBalancedBST<Integer> s = new SortedLinkedListToBalancedBST<Integer>();
        LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        s.convert(list2);
        assertEquals(list2,  s.getInorderList());
    }

    @Test
    public void testThree() {
        SortedLinkedListToBalancedBST<Integer> s = new SortedLinkedListToBalancedBST<Integer>();
        LinkedList<Integer> list3 = new LinkedList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        s.convert(list3);
        assertEquals(list3,  s.getInorderList());
    }

    @Test
    public void testFour() {
        SortedLinkedListToBalancedBST<Integer> s = new SortedLinkedListToBalancedBST<Integer>();
        LinkedList<Integer> list4 = new LinkedList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        s.convert(list4);
        assertEquals(list4,  s.getInorderList());

    }
}

Answer 1

I'm going to post a simpler review than I would if I fully understood this class, but hopefully if you clarify some things, I (or others) can come back and review it more in-depth.

My main problem with this code, is that I don't know what it is trying to do. The class is called SortedLinkedListToBalancedBST, which makes me think that it is some kind of converter utility class. However, the class itself has a private member of TreeNode<T> and doesn't have any public methods which are static or return some kind of BST, so that makes me think that it is just a BST implementation which happens to know how to create a BST from a Linked List. But the class doesn't even have all the functionality of a BST!

You need to decide what this class is going to be and then name it appropriately. Is it a class which knows how to convert from a Linked List to a BST and vice-versa, or is it a BST which knows how to create a BST from a Linked List? (The current name isn't even really all encompassing since the class can get the Linked List from the BST as well.)

Without a better understanding of the purpose of this class, I can't comment on the functionality and implementation, but I can talk about the style:

1. Give your variables better names. ll, lb, and hb are not good names. linkedList is a better name for ll, and for the others, I honestly have no clue what they even are supposed to represent.
2. Give different methods different names. Your two inorder() methods do two completely different things. One adds items to a List. The other gets a tree from an ordered list.
3. convert() seems like it might be more appropriate as a constructor.