what is the most efficient way to search binary search tree?

Question

I have seen a lot of search algorithms to search in a binary sorted tree, but all of them are using the same way: recursion. I know recursion is expensive in comparison to loops, because every time we call the search function, a new stack frame is created for that method, which will eventually use a lot of memory if the binary search tree is too big.

Why can't we search the binary search tree like this:

while (root!=NULL)
{
    if (root->data==data)
        return 0;
    else if (data > root->data)
        root=root->right;
    else
        root=root->left;
}

I think that this way is faster and more efficient than the recursive way, correct me if I am wrong!

I don't need time to measure and compare I am just asking theoretically :) — flashdisk, Aug 09 '14 at 09:25

score 5 · Accepted Answer · edited May 23 '17 at 10:26

5

Probably your way -which is the common way to code that in C- might be faster, but you should benchmark, because some C compilers (e.g. recent GCC when invoked with gcc -O2 ...) are able to optimize most tail calls as a jump (and passing values in registers). tail call optimization means that a call stack frame is reused by the callee (so the call stack stays bounded). See this question.

FWIW, in OCaml (or Scheme, or Haskell, or most Common Lisp implementations) you would code a tail-recursive call and you know that the compiler is optimizing it as a jump.

Recursion is not always slower than loops (in particular for tail-calls). It is a matter of optimization by the compiler.

Read about continuations and continuation passing style. If you know only C, learn some functional language (Ocaml, Haskell, or Scheme with SICP ...) where tail-calls are very often used. Read about call/cc in Scheme.

edited May 23 '17 at 10:26

Community

1
1

answered Aug 09 '14 at 09:12

Basile Starynkevitch

223,805
18
296
547

so, as you have mentioned the stack will hold one frame for the whole recursion?! @Basile – flashdisk Aug 09 '14 at 09:24
2

@flashdisk: Yes, recursive calls in tail position do not allocate a new stack frame if the compiler does this optimization. As Basile said, most functional languages will mandate that the compiler always optimizes tail calls if possible while in C this is not guaranteed (so you should code iteratively if you want to be safe). BTW, if you have some extra time, check out the classic article "lambda, the ultimate goto" - it explains very well why recursive functions dont necessarily need to be less efficient than imperative loops. – hugomg Aug 09 '14 at 21:12

score 0 · Answer 2 · answered Aug 09 '14 at 09:10

0

Yes, that's the normal way of doing it.

answered Aug 09 '14 at 09:10

Zebra North

11,412
7
37
49

I have seen the two ways as a normal way of doing it :) – flashdisk Aug 09 '14 at 09:26

score 0 · Answer 3 · answered Aug 09 '14 at 20:56

Theoretically both your solution and the recursive solution have the same Big Oh complexity. In theory they are both O(log n). If you want performance measured in seconds you need to go practical, write the code of both methods (iterative, recursive), run them and measure the run time.

what is the most efficient way to search binary search tree?

3 Answers3