#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

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

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 -

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 -

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;
 /*
 swapping p and q. We can do this in order to reduce one condition -
 (node.value < q && node.value > p)
 if (p < q) {
 p = p + q;
  q = p - q;
 p = p - q;
 }
 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;
 } 
}

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