Least common ancestor in a binary tree

Question

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

Answer 1

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.