Thread: recursive vs nonrecursive binary tree traversal

  1. #1
    Registered User gaurav9991's Avatar
    Join Date
    Oct 2010
    Location
    Pune, Maharashtra, India
    Posts
    69

    recursive vs nonrecursive binary tree traversal

    which tree traversal method is more efficient? recursive or nonrecursive ?
    Most of the people says that nonrecursiv is more efficient.
    But i have a book of data structure by Langsam, Augenstein and Tenenbaum which says that recursive is more efficient.
    So which is more efficient and by how much difference?

    Thanks in advance.
    binary tree traversal

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Since both approaches are implementing the same algorithm, then it's really down to the skill of the implementer.

    It's not like one approach is O(n) and another is O(n*n).

    What kind of "efficient" are you talking about?
    Recursive can be very efficient to write the code for, but might not perform so well at run-time.
    Whereas a non-recursive implementation takes work to get right, but is a lot better at run-time.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User gaurav9991's Avatar
    Join Date
    Oct 2010
    Location
    Pune, Maharashtra, India
    Posts
    69
    Quote Originally Posted by Salem View Post
    Since both approaches are implementing the same algorithm, then it's really down to the skill of the implementer.

    It's not like one approach is O(n) and another is O(n*n).

    What kind of "efficient" are you talking about?
    Recursive can be very efficient to write the code for, but might not perform so well at run-time.
    Whereas a non-recursive implementation takes work to get right, but is a lot better at run-time.
    Ok. time complexity will remain same. But what about speed of execution? For nonrecursive implementation we have to write push(), pop(), isstackempty(), ...

    Since automatic stack is more efficient than that of an user defined, it will result in performance boost(a little). In recursive code(4-5 lines) there is no extra variable,so no variables are pushed onto stack.

    Please note one thing that i am talking about only binary tree traversals. Let's not talk about 'recursion vs non recursion'.

    I'm not an expert. so please correct me if i'm wrong.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Like I said, quality of implementation.

    For every person who can do 'X' smartly, there will be another person who can screw up 'Y' badly enough for someone to come along and say 'X' is better.

    > For nonrecursive implementation we have to write push(), pop(), isstackempty(), ...
    True, but in an efficient C++ class implementation, these could be inline calls with no call overhead.

    You can't judge efficiency simply by counting lines of code, or apparent function calls.

    Mostly, the topic is pointless.
    - change the programmer
    - change the compiler
    - change the compiler flags
    - change the machine
    All of these can have just as big an impact on the performance of the program as choosing one of two ways to implement the same code.

    > Ok. time complexity will remain same. But what about speed of execution?
    Do you know the difference?
    If an O(N) algorithm takes 5 seconds, as written by one programmer, for one machine, is it still O(N) if it takes 10 seconds when written by another programmer for another machine?
    If you think the answer is "no", then you're missing the point of what I'm trying to tell you.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Adding to what Salem has said, the academic world doesn't usually represent the real world.

    There are a lot of cases where linear algorithms perform superior to other linear algorithms because of some characteristic of the implementation, some tweak of the platform, or just some aspect of the data.

    You can build a non-recursive, non-stack based binary tree traversal algorithm in a lot of ways. You can modify the tree as you go. You can use bit twiddling masks. You can use a "visited" flag if the tree has one. You can use a fairly simple iteration scheme if the tree is strictly balanced.

    You could improve the non-recursive, stack based implementation. You could swap out a linked list based implementation for an array based version. You could build an outside visited nodes using bit twiddling tricks. You could build a stack based on XOR mathematics and the two facts C guarantees for any object. (I'd probably go this route; that no object has a zero address and that no two objects share an address make the implementation obvious.)

    You could even optimize the recursive versions of the algorithm by limiting stack use, keeping the important bits in registers, or using a better function call mechanism. There is a lot of potential depending on your compiler.

    At the end of the day, you aren't going to know which is going to be faster for any given situation. You'll just have to try one and see.

    Soma

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. binary tree traversal
    By nimitzhunter in forum C++ Programming
    Replies: 5
    Last Post: 01-31-2011, 07:13 PM
  2. Constructing Binary Tree From Traversal
    By bennyscuba in forum C Programming
    Replies: 15
    Last Post: 09-24-2009, 04:47 PM
  3. binary tree but iterative, not recursive!
    By budala in forum C Programming
    Replies: 2
    Last Post: 08-06-2009, 12:55 PM
  4. Recursive Tree Traversal
    By John_L in forum C++ Programming
    Replies: 12
    Last Post: 02-17-2008, 08:34 AM