То же дерево | неправильный анализ сложности решения

Question

У меня есть один вопрос, касающийся анализа сложности пространства для решения проблемы кода leetcode: 100. Same Tree

Проблема: Учитывая два двоичных дерева, напишите функцию, чтобы проверить, являются ли они одинаковыми или нет. Два двоичных дерева считаются одинаковыми, если они структурно идентичны и узлы имеют одинаковое значение.

Код решения:

from collections import deque
class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """    
        def check(p, q):
            # if both are None
            if not p and not q:
                return True
            # one of p and q is None
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            return True

        deq = deque([(p, q),])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False

            if p:
                deq.append((p.left, q.left))
                deq.append((p.right, q.right))

        return True

Мой вопрос:

Анализ сложности пространства решения в Leetcode говорит, что это O (N) для полностью неуравновешенного дерева, чтобы сохранить deque. Тем не менее, я думаю, что сложность пространства определенно не O (N). Я использую следующий пример, чтобы показать почему: Предположим, что root = 1, root.left = 2, root.left.left = 3, root.left.left.left = 4, N равно None. Ниже приведены различные этапы deque. Для каждого этапа мы добавляем один элемент и добавляем два, кроме случаев, когда мы встречаемся с N.

[1] -> [2, N] -> [N, 3, N] -> [3, N] -> [N, 4, N] -> [4, N] -> [N, N, N]

Как видно из приведенной выше декы, размер никогда не достигает N (где N - количество узлов)

Я могу сказать, что сложность этого алгоритма не в O (N) (я прав?), Но я не могу точно сказать, что это такое.