CODEWITHSUNDEEP
algorithmcomplexity-theoryspace-complexity
JavaDeveloper
JavaDeveloper

Reputation: 5660

Space complexity of tree traversal without recursion

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); 
    }
}

Upvotes: 2

Views: 1480

Answers (1)

Pradhan
Pradhan

Reputation: 16737

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).

Upvotes: 4

Related Questions