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 v and w as the lowest node in t that has both v and w as descendants where we allow a node to be a descendant of itself 3 5 1 6 2 0 8 7 4 for example the lowest common ancestor lca of nodes 5 and 1 is 3 another example is lca of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the lca definition type root treenode type p treenode type q treenode rtype treenode type root treenode type p treenode type q treenode rtype treenode
def lca(root, p, q):
    
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left is not None and right is not None:
        return root
    return left if left else right