Preorder traversal of a tree I am practising my coding skills on interviewbit. I got one question about preorder (for a tree). This is what I did first:

public class Solution {
   private ArrayList&lt;Integer&gt; result = new ArrayList&lt;Integer&gt;();
   public ArrayList&lt;Integer&gt; preorderTraversal(TreeNode a) {
       if(a == null){
          return result;
       }
       result.add(a.val);
       preorderTraversal(a.left);
       preorderTraversal(a.right);
       return result;
    }
}


Then I googled solutions for the same problem and this is what I found.


public class PreOrder{
    public ArrayList&lt;Integer&gt; preorderTraversal(TreeNode a) {
        ArrayList&lt;Integer&gt; result = new ArrayList&lt;Integer&gt;();
        Stack&lt;TreeNode&gt; stack = new Stack&lt;TreeNode&gt;();
        if(a == null)
            return result;
        stack.push(a);
        while(!stack.isEmpty()){
            TreeNode popped = stack.pop();
            result.add(popped.val);
            if(popped.right != null)
                stack.push(popped.right);
            if(popped.left != null)
                stack.push(popped.left);
        }
        return result;
    }
}



I understood the second method too. What am I asking is the other method better than mine? If yes then how?

NOTE: I am not allowed to change function arguments and return types.
It depends. (As usual.)

The recursive version is easier to read an maintain, and does the job fine for relatively small data sets.

However, when the data set grows large, you create a new stack frame for each recursive call, which may lead to great stack memory usage up to stack overflow. Furthermore, this is comparatively slow.

The second version uses constant stack size and puts all the real memory usage in the heap where it should be. Not using recursion, it is also bound to be faster (on a micro-level only).

Thus, know the problem you solve: for small sets, write nice code and use your version, for big data sets, optimize by unrolling and use the second version.

(BTW: in my university courses, it was generally recommended to use the second version for NP problems due to raw speed - albeit in C at that time.)