0
\$\begingroup\$

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<Integer> result = new ArrayList<Integer>();
   public ArrayList<Integer> 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<Integer> preorderTraversal(TreeNode a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        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.

\$\endgroup\$
2
\$\begingroup\$

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.)

\$\endgroup\$
  • 1
    \$\begingroup\$ "bound to be faster" you can only know by measuring. Both methods are using a stack, the first implicitly and the second explicitly \$\endgroup\$ – Caleth Jun 19 '17 at 8:41
1
\$\begingroup\$

I prefer your first version to the looping one, as you can easily modify it to be inorder and postorder traversal, merely by swapping the positions of result.add(a.val);, preorderTraversal(a.left); and preorderTraversal(a.right);

public class TreeTraversal {
   private ArrayList<Integer> result = new ArrayList<Integer>();
   public ArrayList<Integer> preorderTraversal(TreeNode a) {
       if(a == null){
          return result;
       }
       result.add(a.val);
       preorderTraversal(a.left);
       preorderTraversal(a.right);
       return result;
    }
    public ArrayList<Integer> inorderTraversal(TreeNode a) {
       if(a == null){
          return result;
       }
       inorderTraversal(a.left);
       result.add(a.val);
       inorderTraversal(a.right);
       return result;
    }
    public ArrayList<Integer> postorderTraversal(TreeNode a) {
       if(a == null){
          return result;
       }
       postorderTraversal(a.left);
       postorderTraversal(a.right);
       result.add(a.val);
       return result;
    }
}

What I like about the looping method is that it keeps the ArrayList in local scope, but that can be solved with ArrayList::addAll. This also avoids the wierd looking if(a == null){ return result; } check.

public class TreeTraversal {
   public ArrayList<Integer> preorderTraversal(TreeNode a) {
       if(a == null){
          return ArrayList<Integer>();
       }
       ArrayList<Integer> result = ArrayList<Integer>();
       result.add(a.val);
       result.addAll(preorderTraversal(a.left));
       result.addAll(preorderTraversal(a.right));
       return result;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.