Traversing binary tree iterative or recursive - complexity analysis

Question

I've heard some opinions that iterative lookup in Binary search tree is more efficient than the recursive way, is it true?
(I know that in space terms the recusion is more expensive)

Answer 1

In terms of time complexity (Big O), there should not be any difference if your algorithms are implemented properly. Recursion is usually heavier with respect to space as each recursive call allocates new space on the stack. I am speaking about your particular binary search tree structure, but this is usually also true in general.

Answer 2

There really will be no difference between recursive search and iterative search as you are anyway traversing the height of the tree examining wither the left node or the right node but never both (and this goes for both iterative and recursive) and thereby you always traverse the height of the tree.

Answer 3

Theoretically there is no change. The bigO will be O(n) for unbalanced and O(logn) for balanced BST. Recursive traversal looks clean on paper. But it has lot of overhead. When a function is called recursively the state of the calling function has to be stored in the stack and the control is passed to the called function. But when you do it iteratively, you do not have such overhead. So for practical purposes you should use iterative approach.

If you write a recursive code and if it turns out to be tail recursion, most modern compilers will try to optimize it by converting it to an iterative code.

Answer 4

Much depends on your language implementation! If procedure calls are expensive in your language, then hand-written iteration may be faster. If procedure calls always push the stack, then hand-written iteration may save memory. In a functional language like Scheme, Haskell, ML, etc. (and I think also in a stack-based language like Postscript or FORTH), you can generally expect "tail recursion" as found in a tree lookup operation to be converted to iteration under the hood, so there is no difference. In fact, this particular form of tail recursion (where a function returns the value of a call to itself) is likely be optimized by a compiler that does not even support full tail-call optimization (TCO).