Lowest Common Ancestor of a Binary Tree

def lowestCommonAncestor(root, p, q):
    n = len(root)

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

def lowestCommonAncestor(root, p, q):
    n = len(root)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or root[i] == -1:
            return -1
        if root[i] == p or root[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return root[find(0)]