title: Binary Search Tree in-order traversal using Iterator & Stack - SPACE complexity O(log N)? How?
body: <p>During the phone interview, I was asked to implement Binary Search Tree in-order traversal using an Iterator &amp; Stack (<em>not recursively</em>). I was not allowed to use a parent pointer.</p>
  
  <p>This is the starter code that I was given.</p>
  
  <pre><code>struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}};
  
  class BTIterator
  {
  public:
      BTIterator(TreeNode *root){
  
  
      };
      TreeNode* next() {
  
      }
      bool hasNext() {
  
      }
  
  };
  </code></pre>
  
  <p>Test function:</p>
  
  <pre><code>void TestFunc(TreeNode *root) {
  BTIterator bti(root);
  while(bti-&gt;hasNext()) {
    cout &lt;&lt; bti-&gt;next()-&gt;val &lt;&lt; " ";
  }}
  </code></pre>
  
  <p>I was specifically asked to implement <code>BTIterator</code>, <code>next</code>, <code>hasNext</code> in the above code.</p>
  
  <p>So I did.
  Follow up questions were what are the time &amp; space complexity.
  So I answered time is O(N), space is O(N).
  However, the interviewer said "You can reduce the space complexity further to 
   O(log N)". I asked him how and he said "we only need to store the parents". (I could have heard him wrong. He had a very thick accent.) My implementation was storing every nodes that has left children. I just took his answer for granted.</p>
  
  <p>However, after the interview, I think, even if we only need to store the parents (not the leaf node) it's still O(N). It's precisley O(N/2) but that's still O(N). I believe <strong>any node who has left children</strong> should be stored in the stack. How not to?</p>
  
  <p>The only time when the space O(logN) could be achieved is when the binary tree has only one branch that keeps doing down (not a balanced tree with full leaves.)</p>
  
  <p>What am I missing here? If anyone could explain how the space complexity using the iterator can be reduced further to O(log N), I will appreciate a lot!</p>