1
\$\begingroup\$

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

    }
}
\$\endgroup\$
  • \$\begingroup\$ Is this class supposed to be a BalancedBST or just convert to and from a BalancedBST? \$\endgroup\$ – stiemannkj1 Jun 7 '14 at 15:53
  • \$\begingroup\$ The problem is equivalent to the second phase (vine-to-tree) of a Day–Stout–Warren algorithm. \$\endgroup\$ – CiaPan Jan 20 '16 at 6:02
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.