Космическая сложность обхода дерева без рекурсии

Question

Этот код перемещается по дереву, но не использует рекурсию, заменяя его стеком. Максимальный размер стека должен быть числом узлов на последнем уровне. Является ли пространственная сложность следующего кода: O (высота), где высота корня равна 0?

public void preOrder() { 
    if (root == null) throw new IllegalStateException("the root cannot be null"); 

    final Stack<TreeNode<E>> stack = new Stack<TreeNode<E>>(); 
    stack.add(root); 

    while (!stack.isEmpty()) { 
     final TreeNode<E> treeNode = stack.pop(); 
     System.out.print(treeNode.item + " "); 
     if (treeNode.right != null) stack.add(treeNode.right); 
     if (treeNode.left != null) stack.add(treeNode.left); 
    } 
} 

Answer 1

Единственное использование пространства в коде происходит из элементов в Stack<>. Поскольку, как вы заметили в вопросе, размер Stack<> в любой точке - это глубина текущего узла (т. Е. Расстояние от корня), сложность пространства вашего алгоритма равна O(height). Например, если у вас есть сбалансированное двоичное дерево, O(height) может быть O(log V), где V - количество вершин в вашем дереве. В худшем случае, O(height) = O(V).