title: Recursive vs Iterative Tree Traversal
body: <p>So I was looking at tree traversal algorithms. For example, in a K-d tree traversal, our goal is to traverse the nodes down to the leaf. This isn't so much of a tree search, more just a root to leaf traversal.</p>
  
  <p>In such a case, a recursive solution would suffice. However, in languages like C, calling a function recursively requires pushing values onto the stack and jumping between stack frames etc. The standard recursive method would be something like:</p>
  
  <pre><code>void traverse(Node* ptr){
      if(ptr.left == null &amp;&amp; ptr.right == null) return;
      if(ptr.val &gt;= threshold) traverse(ptr.right);
      else if(ptr.val &lt; threshold) traverse(ptr.left);
  }
  traverse(root);
  </code></pre>
  
  <p>Hence, considering that there's a definite upper bound on binary trees (I'm sure this could be extended to other tree types too), would it be more efficient to perform this traversal iteratively instead:</p>
  
  <pre><code>Node* ptr = root;
  for(int i = 0; i &lt; tree.maxHeight; i++) {
      if (ptr.left == null &amp;&amp; ptr.right == null) break;
      if (ptr.val &gt;= threshold) ptr = ptr.right;
      else if (ptr.val &lt; threshold) ptr = ptr.left
  }
  </code></pre>
  
  <p>The max height of a binary tree would be its number of nodes, while a balanced one would have log(n). Hence I was wondering if there were any downsides to the iterative solution or if it would indeed be faster than plain recursion. Is there any concept I'm missing in this?</p>