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());
 }
}

• stiemannkj1: Is this class supposed to be a BalancedBST or just convert to and from a BalancedBST?
• CiaPan: The problem is equivalent to the second phase (vine-to-tree) of a Day–Stout–Warren algorithm.

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.