From 92cbba10439f362fac325677e99ae93bd1bf5dd6 Mon Sep 17 00:00:00 2001 From: Michael Hunteman Date: Mon, 3 Oct 2022 21:24:17 -0500 Subject: Add Lowest Common Ancestor --- LowestCommonAncestor.java | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 LowestCommonAncestor.java 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); + } +} -- cgit v1.2.3