Binary Search Tree preorder traversal, recursion vs loop?

Question

we can traverse the binary search tree through recursion like:

void traverse1(node t) {
    if( t != NULL) {
        visit(t);
        traverse1(t->left);
        traverse1(t->right);
    }
}

and also through loop( with stack) like:

void traverse2(node root) {
    stack.push(root);
    while (stack.notEmpty()) {
        node next = stack.pop();
        visit(next);
        if (next->right != NULL)
            stack.push(next->right);
        if (next->left != NUll)
            stack.push(next->left)
    }
}

Question

Which one is more efficiency? why?

I think these two method time complexity is both O(n). so all the differences are all in the space complexity or ..?

Answer 1

It will depend on how you define efficiency? It is in runtime, amount of code, size of executable, how much memory/stack space is used, or how easy it is to understand the code?

The recursion is very easy to code, hopefully easy to understand, and is less code. Looping may be a bit more complex (depending on how you view complexity) and code. Recursion may be easier to understand and will be less in the amount of code and in executable size. Recursion will use more stack space assuming you have a few items to transverse.

Looping will have a larger amount of code (as your above example shows), and could possibly be considered a bit more complex. But the transverse is just one call to be place on the stack, rather than several. So if you have a lot of items to transverse, loop will be faster as you don't have the time to push items on the stack and the pop them off, which is what will occur when using recursion.