Recursive Vs iterative Traversal of a BST
<p>If I do recursive traversal of a binary tree of N nodes, it will occupy N spaces in execution stack.
If i use iteration , i will have to use N spaces in an explicit stack.</p>

<p>Question is do we say that recursive traversal is also using <code>O(N)</code> space complexity like iterative one is using?
I am talking in terms of running traversal code on some platform which bounds me by memory limits.
Also i am not talking of directly implementing iteration (in which one can say either of the approaches is fine), I am implementing algorithm for <code>KthSmallestElement()</code> in a BST which uses sort of traversal through the BST.</p>

<p>Should i use iterative approach or recursive approach in terms of space complexity, so that my code doesn't fail in space limits?</p>

<p>Putting it clearly:</p>

<p>Here is what i implemented:</p>

<pre><code>int Solution::kthsmallest(TreeNode* root, int k) {
    stack&lt;TreeNode *&gt; S;
    while(1)
    {
        while(root)
        {
            S.push(root);
            root=root-&gt;left;
        }

        root=S.top();
        S.pop();

        k--;
        if(k==0)
            return root-&gt;val;

        root=root-&gt;right;
    }
}
</code></pre>

<p>Here is what my friend implemented:</p>

<pre><code>class Solution {
    public:
        int find(TreeNode* root, int &amp;k) {
            if (!root) return -1;
            // We do an inorder traversal here. 
            int k1 = find(root-&gt;left, k);
            if (k == 0) return k1; // left subtree has k or more elements.
            k--; 
            if (k == 0) return root-&gt;val; // root is the kth element.
            return find(root-&gt;right, k); // answer lies in the right node.
        }

        int kthsmallest(TreeNode* root, int k) {
           return find(root, k); // Call another function to pass k by reference.
        }
};
</code></pre>

<p><strong>SO Which of the two is better &amp; how?</strong></p>