# Least common ancestor in a binary tree

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


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.

• Yes, you are right, I meant || instead of &&. Wouldn't the swapping make the code kind of difficult to understand? Jan 16, 2015 at 2:34
• @yadav_vi Not at all - the rest would be much easier to follow.
– vnp
Jan 16, 2015 at 6:35
• 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? Jan 16, 2015 at 8:03