Diameter of Binary Tree

def diameterOfBinaryTree(tree):
    nodes = [i for i, value in enumerate(tree) if value != -1]
    best = 0
    for x in range(len(nodes)):
        for y in range(x + 1, len(nodes)):
            a, b = nodes[x], nodes[y]
            edges = 0
            while a != b:
                # A larger index is never higher up, so climb from it.
                if a > b:
                    a = (a - 1) // 2
                else:
                    b = (b - 1) // 2
                edges += 1
            best = max(best, edges)
    return best

def diameterOfBinaryTree(tree):
    n = len(tree)

    def height(i):
        # Nodes on the longest downward path from i; an empty spot has 0.
        if i >= n or tree[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    best = 0
    for i in range(n):
        if tree[i] != -1:
            # The longest path that turns at node i goes down both sides.
            best = max(best, height(2 * i + 1) + height(2 * i + 2))
    return best

def diameterOfBinaryTree(tree):
    n = len(tree)
    best = 0

    def height(i):
        # Returns the height of node i and updates best on the way back up.
        nonlocal best
        if i >= n or tree[i] == -1:
            return 0
        left = height(2 * i + 1)
        right = height(2 * i + 2)
        best = max(best, left + right)  # the longest path that turns at node i
        return 1 + max(left, right)

    height(0)
    return best