treeAlgorithms/LeastCommonAncestor.java

Go to the documentation of this file.

package treeAlgorithms;

public class LeastCommonAncestor<T extends Comparable<T>> {

    public TreeNode<T> findLCA(TreeNode<T> root, T valLess, T valGT) {
        TreeNode<T> found = null;
        if (root != null) {
            Comparable<T> rootVal = root.getValue();
            // if root != valLess && root != valGT
            if (rootVal.compareTo(valLess) != 0
                    && rootVal.compareTo(valGT) != 0) {
                if (root.getLeft() != null) {
                    // if left == valLess || left == valGT then return root
                    Comparable<T> leftVal = root.getLeft().getValue();
                    if (leftVal.compareTo(valLess) == 0
                            || leftVal.compareTo(valGT) == 0) {
                        return root;
                    }
                }
                if (root.getRight() != null) {
                    // if right == valLess || right == valGT then return root
                    Comparable<T> rightVal = root.getRight().getValue();
                    if (rightVal.compareTo(valLess) == 0
                            || rightVal.compareTo(valGT) == 0) {
                        return root;
                    }
                }
                // if valLess < root < valGT then return root
                if (rootVal.compareTo(valLess) > 0
                        && rootVal.compareTo(valGT) < 0) {
                    return root;
                }
                // if root < valLess && root < valGT then findLCA(right, valLess, valGT)
                if (rootVal.compareTo(valLess) < 0
                        && rootVal.compareTo(valGT) < 0) {
                    return findLCA(root.getRight(), valLess, valGT);
                }
                // if root > valLess && root > valGT then findLCA(left, valLess, valGT )
                if (rootVal.compareTo(valLess) > 0
                        && rootVal.compareTo(valGT) > 0) {
                    return findLCA(root.getLeft(), valLess, valGT);
                }
            }
        }
        return found;
    }
}