# Convert sorted linkedlist into balanced binary search tree

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

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);
inorder(node.right, list);
}
}
}

@Test
public void testOne() {
s.convert(list1);
assertEquals(list1,  s.getInorderList());
}

@Test
public void testTwo() {
s.convert(list2);
assertEquals(list2,  s.getInorderList());
}

@Test
public void testThree() {
s.convert(list3);
assertEquals(list3,  s.getInorderList());
}

@Test
public void testFour() {
s.convert(list4);
assertEquals(list4,  s.getInorderList());

}
}

• Is this class supposed to be a BalancedBST or just convert to and from a BalancedBST? Jun 7, 2014 at 15:53
• The problem is equivalent to the second phase (vine-to-tree) of a Day–Stout–Warren algorithm. Jan 20, 2016 at 6:02

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!
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.