<jupyter_start><jupyter_text>[Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”Example 1:```Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output: 3Explanation: The LCA of nodes 5 and 1 is 3.     3   /   \     5     1   / \   / \6  2  0  8  / \ 7  4```Example 2:```Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output: 5Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.     3   /   \     5     1   / \   / \6  2  0  8  / \ 7  4```Example 3:```Input: root = [1,2], p = 1, q = 2Output: 1```**Constraints**:  * The number of nodes in the tree is in the range [2, 105].* $-10^9 <= Node.val <= 10^9$* All Node.val are unique.* p != q* p and q will exist in the tree.<jupyter_code># Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None<jupyter_output><empty_output><jupyter_text>Approach I: Intution $O(n), O(n)$Find the path (depth first search) to each of the two nodes p and q, and then find the last common node. Taking the example 2 to illustrate:Path to p: 3, 5  Path to q: 3, 5, 2, 4So the last common node in their path is 5, which is the lowest ancestor node.<jupyter_code># helper function to return the path from the root to a node with target value

def find_path(root: TreeNode, value:int)-> list:
    def search(node, target):
        if not node:
            return False
        path.append(node.val)
        if node.val == target or search(node.left, target) or search(node.right, target):
            return True
        else:
            path.pop()
            return False

    path = []
    search(root, value)
    return path

def find_lca(root: TreeNode, p:int, q:int) -> int:
    A = find_path(root, p)
    B = find_path(root, q)
    
    i = 0
    while i < len(A):
        if A[i] != B[i]:
            return A[i-1]
        else:
            i += 1
    return A[-1]
# Test the preorder traverse using tree in Example 2 [3,5,1,6,2,0,8,null,null,7,4]

values = [3,5,1,6,2,0,8,None,None,7,4]
nodes = [TreeNode(x) for x in values if x != None]

root = nodes[0]
nodes[0].left, nodes[0].right = nodes[1], nodes[2]
nodes[1].left, nodes[1].right = nodes[3], nodes[4]
nodes[2].left, nodes[2].right = nodes[5], nodes[6]
nodes[4].left, nodes[4].right = nodes[7], nodes[8]

assert find_lca(root, 5, 1) == 3
assert find_lca(root, 5, 4) == 5
assert find_lca(root, 1, 2) == 3
assert find_lca(root, 6, 4) == 5<jupyter_output><empty_output><jupyter_text>Approach II: Smart recusion> It's recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.  by StefanPochmann, https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/65225/4-lines-C%2B%2BJavaPythonRuby<jupyter_code># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root in (None, p, q): return root
        left, right = (self.lowestCommonAncestor(kid, p, q)
                       for kid in (root.left, root.right))
        return root if left and right else left or right<jupyter_output><empty_output><jupyter_text>(Variant) 235. Lowest Common Ancestor of a Binary Search Treehttps://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”  Approach: RecusionIt is easier to know the LCA's location based on the product of the different of these two values $product = (root.val - p.va) * (root.val - q.val)$ to the root:* product  LCA is the current node since one is on its left and the other one is on the right* product > 0:    - LCA is on the left sub-tree if p  0)    - LCA is on the right sub-tree otherwise<jupyter_code># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        while (root.val - p.val) * (root.val - q.val) > 0:
            root = (root.left, root.right)[p.val > root.val]  # amazing grama
        return root<jupyter_output><empty_output><jupyter_text>(Variant) 1644. Lowest Common Ancestor of a Binary Tree IIhttps://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/The given node p or q may not in the binary tree, and return None in this case.**Constraints**:  * The number of nodes in the tree is in the range [1, 104].* $-10^9 <= Node.val <= 10^9$* All Node.val are unique.* p != q **Follow up**:Can you find the LCA traversing the tree, without checking nodes existence?<jupyter_code>### Approach 1: Reuse the algorithm when both nodes are in the tree

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        A = self.find_path(root, p)
        B = self.find_path(root, q)

        if not A or not B: return None
        for e in reversed(A):
            if e in set(B):
                return e
    
    def find_path(self, root: TreeNode, value: TreeNode)-> list:
        def search(node, target):
            if not node:
                return False
            path.append(node)
            if node == target or search(node.left, target) or search(node.right, target):
                return True
            else:
                path.pop()
                return False

        path = []
        search(root, value)
        return path<jupyter_output><empty_output><jupyter_text>Appraoch 2: Use a flag to record whether these two nodes are found  (Variant) 1650. Lowest Common Ancestor of a Binary Tree IIIGiven two nodes of a binary tree p and q, return their lowest common ancestor (LCA).Each node will have **a reference to its parent node**. The definition for Node is below:```class Node {    public int val;    public Node left;    public Node right;    public Node parent;}```According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."**Constraints**:* The number of nodes in the tree is in the range [2, 105].* $-10^9 <= Node.val <= 10^9$* All Node.val are unique.* p != q* p and q exist in the tree.<jupyter_code>"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        A = []
        while p:
            A.append(p)
            p = p.parent
        
        B = []
        while q:
            B.append(q)
            q = q.parent
        
        t = set(B)
        for e in A:
            if e and e in t:
                return e<jupyter_output><empty_output><jupyter_text>Approach 1: Two pointers to find the common element in two linked listThis is like the smart algorithm to find the first common element in two linked list. Go through the list using two pointers and switch the pointer when one reaches to the end.refs: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/discuss/932499/Simple-Python-Solution-with-O(1)-space-complexity<jupyter_code>"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        p1, p2 = p, q
        while p1 != p2:
            p1 = p1.parent if p1.parent else q
            p2 = p2.parent if p2.parent else p
            
        return p1<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10796561604584527, 'fraction_numerical': 0.02166189111747851, 'mean_word_length': 2.7226962457337884, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 39, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '441401', 'license': 'Apache-2.0', 'n_tokens_mistral': 2905, 'n_tokens_neox': 2757, 'n_words': 1091, 'path': 'tree/Lowest Common Ancestor of a Binary Tree LCA.ipynb', 'repo_name': 'iShiBin/algorithm', 'size': '8725'}