JavaAlgorithms
Elementary and no so elementary Java algorithms
treeAlgorithms/LeastCommonAncestor.java
Go to the documentation of this file.
00001 
00009 package treeAlgorithms;
00010 
00032 public class LeastCommonAncestor<T extends Comparable<T>> {
00033 
00045     public TreeNode<T> findLCA(TreeNode<T> root, T valLess, T valGT) {
00046         TreeNode<T> found = null;
00047         if (root != null) {
00048             Comparable<T> rootVal = root.getValue();
00049             // if root != valLess && root != valGT
00050             if (rootVal.compareTo(valLess) != 0
00051                     && rootVal.compareTo(valGT) != 0) {
00052                 if (root.getLeft() != null) {
00053                     // if left == valLess || left == valGT then return root
00054                     Comparable<T> leftVal = root.getLeft().getValue();
00055                     if (leftVal.compareTo(valLess) == 0
00056                             || leftVal.compareTo(valGT) == 0) {
00057                         return root;
00058                     }
00059                 }
00060                 if (root.getRight() != null) {
00061                     // if right == valLess || right == valGT then return root
00062                     Comparable<T> rightVal = root.getRight().getValue();
00063                     if (rightVal.compareTo(valLess) == 0
00064                             || rightVal.compareTo(valGT) == 0) {
00065                         return root;
00066                     }
00067                 }
00068                 // if valLess < root < valGT then return root
00069                 if (rootVal.compareTo(valLess) > 0
00070                         && rootVal.compareTo(valGT) < 0) {
00071                     return root;
00072                 }
00073                 // if root < valLess && root < valGT then findLCA(right, valLess, valGT)
00074                 if (rootVal.compareTo(valLess) < 0
00075                         && rootVal.compareTo(valGT) < 0) {
00076                     return findLCA(root.getRight(), valLess, valGT);
00077                 }
00078                 // if root > valLess && root > valGT then findLCA(left, valLess, valGT )
00079                 if (rootVal.compareTo(valLess) > 0
00080                         && rootVal.compareTo(valGT) > 0) {
00081                     return findLCA(root.getLeft(), valLess, valGT);
00082                 }
00083             }
00084         }
00085         return found;
00086     }
00087 }
 All Classes Namespaces Files Functions Variables