0
\$\begingroup\$

I saw this implementation of Least common ancestor and thought that it was very inefficient as it used Queues. I have tried to implement it using a normal tree traversal.

I have also tried to keep all the utility methods as public static so that they could be accessed from anywhere. Is the implementation correct? I have added some test cases and they seem to run fine.

Could someone suggest what all things can be improved for the following -

  • The algorithm itself.
  • Object oriented usage.

LeastCommonAncestor

public class LeastCommonAncestor {

    private List<Integer> listOfNodes;
    public TreeNode root;

    public LeastCommonAncestor(List<Integer> list) {
        listOfNodes = list;
        root = createTree(listOfNodes);
    }

    public static class TreeNode {
        TreeNode left;
        TreeNode right;
        int value;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    public static TreeNode createTree(List<Integer> list) {
        TreeNode root = null;
        TreeNode temp, temp2;
        for (Integer integer : list) {
            if (root == null) {
                root = new TreeNode(integer);
                root.left = null;
                root.right = null;
                continue;
            }
            temp = root;
            temp2 = root;
            while (temp != null) {
                temp2 = temp;
                temp = (temp.value < integer) ? temp.right : temp.left;
            }

            if (temp2.value < integer) {
                temp2.right = new TreeNode(integer);
            } else {
                temp2.left = new TreeNode(integer);
            }
        }

        return root;
    }

    public static void printTree(TreeNode root) {
        if (root == null) return;
        System.out.print(root.value + " ");
        printTree(root.left);
        printTree(root.right);
    }

    public static boolean isInTree(TreeNode root, int p) {
        TreeNode node = root;
        while (node != null) {
            if (node.value == p) return true;
            node = (node.value < p) ? node.right : node.left;
        }
        return false;
    }

    public static int getLeastCommonAncestor(TreeNode root, int p, int q) {
        if (root == null) {
            throw (new IllegalArgumentException("root shouldn't be null"));
        }

        TreeNode node = root;
        while (node != null) {
            if (node.value == p || node.value == q)
                return node.value;
            if ((node.value < p && node.value > q)
                    && (node.value < q && node.value > p)) {
                return node.value;
            }

            node = (node.value < p && node.value < q) ? node.right : node.left;
        }
        return root.value;
    }       
}

Test Cases

public class LeastCommonAncestorTest {

    @Test
    public void testOneItem() {
        LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1));
        assertEquals(1,
                LeastCommonAncestor.getLeastCommonAncestor(lcs.root, 1, 1));
    }

    @Test
    public void testTwoItem() {
        LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2));
        assertEquals(1,
                LeastCommonAncestor.getLeastCommonAncestor(lcs.root, 1, 2));
    }

    @Test
    public void testItem1AndItem2Unique() {
        LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2,
                3, 4, 5, 6, 7));
        assertEquals(4,
                LeastCommonAncestor.getLeastCommonAncestor(lcs.root, 4, 6));
    }

    @Test
    public void testItem1ParentOfItem2() {
        LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2,
                3, 4, 5, 6, 7));
        assertEquals(2,
                LeastCommonAncestor.getLeastCommonAncestor(lcs.root, 2, 4));
    }

    @Test
    public void testItem1SameAsItem2() {
        LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2,
                3, 4, 5, 6, 7));
        assertEquals(2,
                LeastCommonAncestor.getLeastCommonAncestor(lcs.root, 2, 2));
    }

    @Test
    public void testItem1SameAsItem2SameAsRoot() {
        LeastCommonAncestor lcs = new LeastCommonAncestor(Arrays.asList(1, 2,
                3, 4, 5, 6, 7));
        assertEquals(1,
                LeastCommonAncestor.getLeastCommonAncestor(lcs.root, 1, 1));
    }
}
\$\endgroup\$
1
\$\begingroup\$

The logic in

        if ((node.value < p && node.value > q)
                && (node.value < q && node.value > p)) {
            return node.value;
        }

doesn't sound right. The condition is never satisfied. You probably meant to || the outer terms. In any case, I recommend to check that p < q at the beginning of getLeastCommonAncestor, and swap them if not. This will save you a redundant test.

\$\endgroup\$
  • \$\begingroup\$ Yes, you are right, I meant || instead of &&. Wouldn't the swapping make the code kind of difficult to understand? \$\endgroup\$ – yadav_vi Jan 16 '15 at 2:34
  • \$\begingroup\$ @yadav_vi Not at all - the rest would be much easier to follow. \$\endgroup\$ – vnp Jan 16 '15 at 6:35
  • \$\begingroup\$ I have made some changes in my code, is this what you were saying? Also what about other things like Classes - should I keep TreeNode as static or should I make it an independent class? \$\endgroup\$ – yadav_vi Jan 16 '15 at 8:03

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.