Add Lowest Common Ancestor

1 files changed, 28 insertions, 0 deletions

diff --git a/LowestCommonAncestor.java b/LowestCommonAncestor.java
new file mode 100644
index 0000000..5eb08de
--- /dev/null
+++ b/LowestCommonAncestor.java
@@ -0,0 +1,28 @@
+import java.lang.*;
+import java.util.*;
+import node.*;
+
+class LowestCommonAncestor {
+	public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+		if (root == null)
+			return null;
+		else if (p.val < root.val && q.val < root.val)
+			return lowestCommonAncestor(root.left, p, q);
+		else if (p.val > root.val && q.val > root.val)
+			return lowestCommonAncestor(root.right, p, q);
+		return root;
+	}
+
+	public static void main(String[] args) {
+		TreeNode leftLeaf = new TreeNode(0);
+		TreeNode lMiddleLeaf = new TreeNode(3);
+		TreeNode rMiddleLeaf = new TreeNode(5);
+		TreeNode lRightLeaf = new TreeNode(7);
+		TreeNode rRightLeaf = new TreeNode(9);
+		TreeNode lowerLeftParent = new TreeNode(4, lMiddleLeaf, rMiddleLeaf);
+		TreeNode leftParent = new TreeNode(2, leftLeaf, lowerLeftParent);
+		TreeNode rightParent = new TreeNode(8, lRightLeaf, rRightLeaf);
+		TreeNode root = new TreeNode(6, leftParent, rightParent);
+		System.out.println(lowestCommonAncestor(root, leftLeaf, lowerLeftParent).val);
+	}
+}