Recursive vs Iterative Tree Traversal

Question

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.

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:

void traverse(Node* ptr){
    if(ptr.left == null && ptr.right == null) return;
    if(ptr.val >= threshold) traverse(ptr.right);
    else if(ptr.val < threshold) traverse(ptr.left);
}
traverse(root);

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:

Node* ptr = root;
for(int i = 0; i < tree.maxHeight; i++) {
    if (ptr.left == null && ptr.right == null) break;
    if (ptr.val >= threshold) ptr = ptr.right;
    else if (ptr.val < threshold) ptr = ptr.left
}

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?

Jim Mischel Jim Mischel · Accepted Answer · 2019-07-23T04:59:15

Your code isn't so much a tree traversal as it is a tree search. If all you want to do is go from the root to a leaf, then the iterative solution is simpler and faster, and will use less memory because you don't have to deal with stack frames.

If you want a full traversal of the tree: that is, an in-order traversal where you visit every node, then you either write a recursive algorithm, or you implement your own stack where you explicitly push and pop nodes. The iterative method where you implement your own stack will potentially be faster, but you can't avoid the O(log n) (in a balanced binary tree) or the possible O(n) (in a degenerate tree) memory usage. Implementing an explicit stack will use somewhat less memory, simply because it only has to contain tree node pointers, whereas a full stack frame contains considerably more.

Recursive vs Iterative Tree Traversal

1 Answers