def get_chain(root, val, chain):
    if not root:
        return None
    if root.info == val:
        chain = chain + (root,)
        return chain
    left_result = get_chain(root.left, val, chain)
    if left_result:
        return left_result + (root,)
    right_result = get_chain(root.right, val, chain)
    if right_result:
        return right_result + (root,)
    return chain


def lca(root, v1, v2):
    x = get_chain(root, v1, ())
    y = get_chain(root, v2, ())
    x = list(x)
    y = set(y)
    common = None
    for i in range(len(x)):
        if x[-(i+1)] in y:
            common = x[-(i+1)]
    return common

from collections import deque

def lca(root, v1, v2):
    if root is None: 
        return None
    
    # Find path from root to target node
    def findPathToTarget(root, target_int):
        dq = deque([(root, [])])
        while dq:
            node, path = dq.popleft()
            new_path = path + [node]  # Create a new path list
            if node.info == target_int:
                return new_path
            if node.left:
                dq.append((node.left, new_path))
            if node.right:
                dq.append((node.right, new_path))
        return []

    # Get paths to v1 and v2
    path_to_v1 = findPathToTarget(root, v1)
    path_to_v2 = findPathToTarget(root, v2)

    # Compare paths to find LCA
    lca = None
    for a, b in zip(path_to_v1, path_to_v2):
        if a == b:
            lca = a
        else:
            break
    return lca

public Node LowestCommonAncestor(Node n1, Node n2)
{
    if (n1.FindNode(n2.Data) != null) return n1;
    if (n2.FindNode(n1.Data) != null) return n2;
    if(n1.Parent ==  n2.Parent) return n1.Parent;
    return LowestCommonAncestor(n1.Parent, n2.Parent);
}