Least common ancestor for binary search tree

Question

I want you to pick my code apart and give me some feedback on how I could make it better or more simple. This code finds a common ancestor for binary search tree. This code accounts duplicates as well as incomplete tree, and also throws an exception if input element is not in the tree.

public class LeastCommonAncestorBST {

 private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        TreeNode right;
        int item;

        TreeNode (TreeNode left, TreeNode right, int item) {
            this.left = left;
            this.right = right;
            this.item = item;
        }
    }

    public void makeBinarySearchTree(Integer[] a) {
        for (int i : a) {
            addElement(i);
        }
    }

    public void addElement(int element) {
        if (root == null) {
            root = new TreeNode(null, null, element);
        } else {
            TreeNode prevNode = null;
            TreeNode node = root;

            while (node != null) {
                prevNode = node;
                if (element <= node.item) {
                    node = node.left;
                } else {
                    node = node.right;
                }
            }

            if (element <= prevNode.item) {
                prevNode.left = new TreeNode(null, null, element);
            } else {
                prevNode.right = new TreeNode(null, null, element);
            }
        }
    }


    public int leastCommonAncestor(int n1, int n2) {
        TreeNode node  = findLCA(root, n1, n2);
        if (node != null) {
            return node.item;
        } else {
            throw new IllegalArgumentException(" Input was not valid ");
        }
    }

    private TreeNode findLCA(TreeNode node, int n1, int n2) {

        if (node == null) return null;

        if (node.item > n1 && node.item > n2) {
            return findLCA(node.left, n1, n2);
        } 

        if (node.item < n1 && node.item < n2) {
            return findLCA(node.right, n1, n2);
        }

        boolean bothExist = doesExist(node, n1) && doesExist(node, n2);

        return bothExist ? node : null;
    }

    private boolean doesExist(TreeNode node, int n) {
        if (node == null) {
            return false;
        }
        if (n < node.item) {
            return doesExist(node.left, n);
        } 

        if (n > node.item ) {
            return doesExist(node.right, n);
        }
        return true;
    }
}

Answer 1

Most of the code is pretty good!

I find your interface a bit weird. Instead of public void makeBinarySearchTree(Integer[] a), I suggest public void addElements(int[] elements) to be consistent with your addElement(int) method. There's no need to tell everyone that you're making a binary search tree, since that information is encoded into your class name already.

You might want to generalize the code to handle any Comparable, not just ints. You would get more flexibility for little additional effort.

Instead of throwing IllegalArgumentException, I would throw NoSuchElementException. In fact, I would change doesExist() to

private TreeNode find(TreeNode start, int element) {
    if (start == null) {
        throw new NoSuchElementException(Integer.toString(element));
    }
    if (element < start.item) {
        return find(start.left, element);
    }
    if (element > start.item) {
        return find(start.right, element);
    }
    // Assertion makes the code more readable
    assert element == start.item;
    return start;
}

That way, you can let the exception propagate up all the way, and it would tell you which of the two numbers passed to leastCommonAncestor() is missing.

Your addElement() is a bit repetitive and can be simplified:

public void addElement(int element) {
    // No matter what happens, we're going to attach this
    // new node somewhere.
    TreeNode newNode = new TreeNode(null, null, element);

    if (root == null) {
        root = newNode;
        return;  // Return early to avoid a layer of nesting
    }

    TreeNode node = root;
    while (true) {
        if (element <= node.item) {
            // Test for null before following the pointer.
            // That relieves you from having to keep track
            // of the parent node, and also avoids having
            // to decide again whether to attach to the
            // left or right.
            if (node.left == null) {
                node.left = newNode;
                return;
            }
            node = node.left;
        } else {
            if (node.right == null) {
                node.right = newNode;
                return;
            }
            node = node.right;
        }
    }
}

Follow-Up Q & A

Not understanding your feedback - I suggest public void addElements(int[] elements) to be consistent with your addElement(int) method.

In Java, you use unboxed primitives most of the time. Boxed types are rare: generally they are only used in Collections (which can't store primitives) and when you want to store a value that might be null. An Integer[] array is therefore rather unnatural — it's neither an int[] nor a List<Integer>, both of which would be more likely to occur.

As regards to cleaning up addElement() I had few concerns

1. while(true) is said to be bad

2. more checks in your method (a) while(true) (b) null check (c) comparison, while my code does only 2 of them for most traversal part (a) null and (b) compare.

There are two common objections to while (true): one invalid concern about efficiency, and one legitimate concern about style.

Many decades ago, simplistic C compilers might take while (true) literally, and generate code to load 1 into a register, check whether the register was non-zero, and execute a conditional jump. Modern C compilers and all Java compilers are smart enough to handle while (true) efficiently, generating nothing but an unconditional goto at the end of the loop. You can verify this by inspecting the bytecode:

$ cat WhileTrue.java
public class WhileTrue {
    private WhileTrue() {}  // Suppress default constructor

    public static void main(String[] args) {
        System.out.println("Before while loop");
        while (true) {
            System.out.println("In while loop");
        }
        // Compiler would detect this as unreachable
        // System.out.println("After while loop");
    }
}

$ javap -c WhileTrue
Compiled from "WhileTrue.java"
public class WhileTrue extends java.lang.Object{
public static void main(java.lang.String[]);
  Code:
   0:   getstatic   #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   3:   ldc #3; //String Before while loop
   5:   invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   8:   getstatic   #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   11:  ldc #5; //String In while loop
   13:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   16:  goto    8

}

That means that your second objection is invalid, since while (true) is not a check. In fact, your original version had more conditionals since you had to decide which side to append to after exiting the loop.

As previously mentioned, there is another problem with while (true), which is that it keeps the reader in suspense. Most programs are not intended to run in an infinite loop. Therefore, when you see while (true), you immediately suspect that something within the loop must eventually cause it to terminate: a break, a return, or an exception. Therefore, whenever you feel the urge to write while (true), it's always worthwhile to think about whether it is possible to restructure the code such that the termination condition can be expressed in the loop header, rather than buried in the loop body. In many instances, it is possible, but here, I think that my proposal is already optimal.