# Lowest Common Ancestor ## Intro This is classic problem of binary tree. It has a lot of practical usages and motivations behind it. For example, we want to find the lowest tag that two elements have access to in a DOM tree. Or we want to find the smallest interval in a segment tree. ## LCA of a Binary Tree ([LC.236](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)) > Given a binary tree, find the lowest common ancestor of two given nodes in the tree. ## Example ``` + 4 / \ 3 7 / \ 5 6 Input: LCA(3,5) Output: 4 Input: LCA(5,6) Output: 7 Input: LCA(6,7) Output: 7 ``` Assume two nodes are in the tree. ## Analysis Obviously, traversing won't work well because we can't visit each node only once from top down. Now we have to come up with a task, the same task, for both the left subtree and the right subtree. 4 cases for the root: 1. LCA in is leftSubtrees 2. LCA is in rightSubtree 3. root is the LCA 4. LCA doesn't exist If you can find LCA, return the LCA. If you can only find p/q, then return p/q. ``` base if root == null return null if root == A or root == B return root divide assign findLCA to leftsSubtree assign findLCA to rightSubtree conquer 4 cases for LCA 1. left != null && right != null then root is the LCA 2. left != null && right == null then left is the LCA 3. left == null && right != null then right is the LCA 4. LCA doesn't exist in this subtree ``` ## Problematic Code ```java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // base case if (root == null) return null; if (root == p || root == q) return root; // divide TreeNode leftLCA = lowestCommonAncestor(root.left, p, q); TreeNode rightLCA = lowestCommonAncestor(root.right, p, q); // conquer if (leftLCA != null && rightLCA != null) return root; if (leftLCA != null) return leftLCA; if (rightLCA != null) return rightLCA; return null; } ``` This piece of code is problematic for several reasons. The first one is the way we define the state. The return type can be a LCA or a target node we have found. This will cause problems in the follow up question. ## Follow up #1 ([LI.578](http://www.lintcode.com/en/problem/lowest-common-ancestor-iii/)) What if node1 or node2 might not exist in the tree? Return null in that case. ## Analysis Previous, the program will return node1 or node2 if the other does not exist in the tree. Now we need to distinguish these two cases.\ 1\. node2 is a descendant of node1\ 2\. node2 is not in the current tree ## Examples Lesson Always do a few examples (exhaust all cases) before talk about your approach. ``` Test Cases: Case 1: node1 and node2 in the left subtree (CHECK) we can't early terminate when root == node1 or root == node2 we need to travel all the way down Case 2: node1 and node2 in the right subtree (CHECK) Case 3: node1 in the left subtree, node2 in the right subtree (CHECK) Case 4: node1 is the root, node2 in the right subtree (CHECK) Case 5: node1 and node2 are the root (CHECK) Case 6: node1 is the left subtree, node2 is in a separate tree (CHECK) ``` ## Approach ``` base if root == null return (null, null) // if root == node1 or root == node2 divide left = lcaHelper(root.left, node1, node2) right = lcaHelper(root.right, node1, node2) merge already found lca if left.lca != null: return left if right.lca != null: return right the current root is the lca if root == node1 && root == node2 return (null, root) if left.targetNode != null and right.targetNode != null return (null, root) if root == node1 || root == node2 if left.targetNode != null return (null, root) else if right.targetNode != null return (null, root) else return (root, null) // current root is a targetNode the current root is not the lca pass along the info if left.targetNode != null return left else return right ``` ## Refined Code ```java private class LCAType { TreeNode targetNode; TreeNode lca; public LCAType(TreeNode node1, TreeNode lca) { targetNode = node1; this.lca = lca; } } public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode node1, TreeNode node2) { LCAType result = lcaHelper(root, node1, node2); return result.lca; } private LCAType lcaHelper(TreeNode root, TreeNode node1, TreeNode node2) { // base if (root == null) { return new LCAType(null, null); } // divide LCAType left = lcaHelper(root.left, node1, node2); LCAType right = lcaHelper(root.right, node1, node2); // merge // already found lca if (left.lca != null) return left; if (right.lca != null) return right; // current root is lca if (root == node1 && root == node2) { return new LCAType(null, root); } if (left.targetNode != null && right.targetNode != null) { return new LCAType(null, root); } // current root is a target node if (root == node1 || root == node2) { if (left.targetNode != null || right.targetNode != null) { return new LCAType(null, root); } else { return new LCAType(root, null); } } // current root is not a lca nor a target node, just pass along the info if (left.targetNode != null) return left; else return right; } ``` ## Follwo Up #2 ([LI.474](http://www.lintcode.com/en/problem/lowest-common-ancestor-ii/)) Given parent pointers ## Follow Up #3 Find all common ancestors. You can need to store the path to root in an array list. Then find intersection of two arrays. ## References * [Finding the Lowest Common Ancestor](http://www.stoimen.com/blog/2012/08/24/computer-algorithms-finding-the-lowest-common-ancestor/) by stoimen * Crack the Coding Interview Ch4 Q7 Solution --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/lowest-common-ancestor.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.