JavaAlgorithms
Elementary and no so elementary Java algorithms
|
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 }