title: What is the space complexity for an iterative preorder traversal in a Binary tree?
body: <p>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 </p>
  
  <blockquote>
    <p><em>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.</em></p>
  </blockquote>
  
  <p>Following is the code for reference :</p>
  
  <pre><code>struct Node{
     int data;
     struct Node* left, right;
  }
  void printPreOrder(struct Node* root){
    if(!root)
     return ;
    stack&lt;struct Node* &gt; s;
    s.push(root);
    while(!s.empty()){
       struct Node *root_element = s.top();
       cout&lt;&lt;root_element-&gt;data&lt;&lt;" ";
       s.pop();
        if(root_element-&gt;right){
           s.push(root_element-&gt;right);
        }
        if(root_element-&gt;left){
           s.push(root_element-&gt;left);
        }
       }
       cout&lt;&lt;endl;
    }
    return ;
  }
  </code></pre>
  
  <p><strong>My intuition</strong></p>
  
  <p>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))).  </p>