Space complexity of tree traversal without recursion

Question

This code traverses the tree, but does not use recursion, substituting it with a stack. The max size of the stack, should be the number of nodes in the last level. Is the space complexity of the following code: O(height), where height of root is 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); 
    }
}

yes you are correct, but isn't O(2^height) same as O(N) where N is number of nodes in tree in worst case. Also maximum size of stack can be N in worst case — sashas

Pradhan Pradhan · Accepted Answer · 2014-12-25T23:42:10

The only space usage in your code comes from elements in your Stack<>. Since, as you observed in the question, the size of Stack<> at any point is the depth of the current node(i.e., distance from the root), the space complexity of your algorithm is O(height). If you have a balanced binary tree, for example, O(height) could be as low as O(log V), where V is the number of vertices in your tree. In the worst case, O(height) = O(V).

Space complexity of tree traversal without recursion

1 Answers