Времева сложност на проверката дали едно двоично дърво е балансирано

Практикувам някои въпроси за интервю и се опитвам да разбера времевата сложност на моето решение, за да определя дали дадено двоично дърво е балансирано.

Вярвам, че решение 2 има времева сложност O(n), докато решение 1 има времева сложност O(n^2). Това се дължи на факта, че в решение 1 се връщате надолу към дъното на дървото, за да проверите дали дървото е балансирано и също така проверявате за разлики във височината на поддървото. Допълнителната сложност идва, когато отиваме по-високо нагоре в дървото към корена, get_height все още рекурсира надолу в дървото, за да изчисли височината. Следователно, пътуване надолу по дървото още веднъж --> O(n^2).

Фактът, че решение 2 първо сравнява височината, означава, че докато се движим обратно нагоре по дървото, не трябва да се връщаме надолу, за да проверим височината на поддървото.

помощник:

def get_height(root):
    if root is None:
        return 0
    else:
        return max(get_height(root.left), get_height(root.right)) + 1

Решение 1:

def is_balanced(root):
    if root is None:
        return True
    else:
        return is_balanced(root.right) and is_balanced(root.left) and (abs(get_height(root.left) - get_height(root.right)) < 2)

Решение 2:

def is_balanced2(root):
    if root is None:
        return True
    else:
        return (abs(get_height(root.left) - get_height(root.right)) < 2) and is_balanced(root.right) and is_balanced(root.left)

код за проверка на часовите разлики:

s = time.time()
print("result: {}".format(is_balanced(a)))
print("time: {}".format(time.time() - s))

s = time.time()
print("result: {}".format(is_balanced2(a)))
print("time: {}".format(time.time() - s))

резултати за небалансирано дърво:

result: False
time: 2.90870666504e-05    # solution 1
result: False
time: 1.50203704834e-05    # solution 2