What is the space complexity for an iterative preorder traversal in a Binary tree?

Question

I have been wondering what would be the space complexity for an iterative preorder traversal(using stack) for a Binary tree. I have referenced Elements of Programming Interviews and they stated that

The space complexity is O(h), where h is the height of the tree, since, with the exception of the top of the stack, the nodes in the stack correspond to the right children of the nodes on the path beginning at the root.

Following is the code for reference :

struct Node{
   int data;
   struct Node* left, right;
}
void printPreOrder(struct Node* root){
  if(!root)
   return ;
  stack<struct Node* > s;
  s.push(root);
  while(!s.empty()){
     struct Node *root_element = s.top();
     cout<<root_element->data<<" ";
     s.pop();
      if(root_element->right){
         s.push(root_element->right);
      }
      if(root_element->left){
         s.push(root_element->left);
      }
     }
     cout<<endl;
  }
  return ;
}

My intuition

While going through the algorithm I observed that the maximum number of entries in a stack at any instance can be max(num_of_leaves_in_left_subtree+1, num_of_trees_in_right_subtree). From this we can deduce that for a tree of height h, the maximum number of leaves can be 2^h. So, the maximum number of trees in left subtree would be 2^(h-1). Thus, the maximum number of entries in the stack would be 2^(h-1)+1. Thus, according to me, the space complexity for the above algorithm would be O(2^(log(n))).

Answer 1

First of all, your iterative implementation of preorder traversal has a mistake - you should push a right node and then a left one, but not vice versa.

Now the explanation - on each iteration you're going one level deeper and adding 2 elements (right and left if they exist) to the stack while popping one node out (the parent one). It means that at most 1 new element is added as you go 1 level down. Once you reach the left most node and pop it out you repeat the same procedure for the top node in the stack -> O(h).

For instance,

      1
     / \
   2     5
  / \   / \
 3   4 6   7

Step 0: 1 is added to the stack -> O(1)

Step 1: 1 removed, 2 and 5 are added -> O(2)

Step 2: 2 removed, 3 and 4 are added -> O(3)

Step 3: 3 removed -> O(2)

Step 4: 4 removed -> O(1)

Step 5: 5 removed, 6 and 7 are added -> O(2)

Step 6: 6 removed -> O(1)

Step 7: 7 removed -> O(0)

As you could see the space complexity was always proportional to the height of the tree.

In the worst case scenario (if tree looks like a list), the space complexity is O(1) for your implementation (as pointed out by @Islam Muhammad) because at each iteration of the while loop, one item is removed from the stack and one item is added (there's only 1 child).