Recursive Preorder Traversal

Question

For today, I tackled this coding challenge question: Given a binary tree, write a method to recursively traverse the tree in the preorder manner. Mark a node as visited by adding its data to the list - Arraylist preorderedList

ArrayList<Integer> preorderedList = new ArrayList<Integer>();
public void preorder(TreeNode root) {

   if(root == null){
       return;
   }
    preorderedList.add(root.data);
    if(root.left != null){
        preorder(root.left);
    }
     if(root.right != null){
        preorder(root.right);
    }

}

Answer 1

It is weird to put an object field right next to the method that uses it. It's more common to put all the object fields together. Of course, you don't show the rest of the class definition, so perhaps this is something you did just for this.

Consider writing instead

List<Integer> preorderedList = new ArrayList<Integer>();

It won't make much difference here, but using the interface as the type makes it easier to change implementations later.

You can simplify the null handling by changing

public void preorder(TreeNode root) {

   if(root == null){
       return;
   }
    preorderedList.add(root.data);
    if(root.left != null){
        preorder(root.left);
    }
     if(root.right != null){
        preorder(root.right);
    }

}

to

public void preorder(TreeNode root) {
    if (root == null) {
        return;
    }

    preorderedList.add(root.data);
    preorder(root.left);
    preorder(root.right);
}

This way it does the check for null after the recursive call rather than before making it. Slightly less efficient, but easier to read. Alternately, if that efficiency is important, note that this makes an extra check. Consider breaking it into two methods. This could be something like

private void _preorder(TreeNode root) {
    preorderedList.add(root.data);

    if (root.left != null) {
        _preorder(root.left);
    }

    if (root.right != null) {
        _preorder(root.right);
    }
}

public void preorder(TreeNode root) {
    if (root == null) {
        return;
    }

    _preorder(root);
}

This only checks if root is null the first time. On the recursive calls, this isn't necessary. It makes one extra method call (which may be inlined) rather than an extra call per leaf. And it only checks for null once for each node rather than twice.

Benchmark, as you may find that the compiler already does this for you.