0

I have two different ways to traverse a tree adt that essentially do the same thing except one is a recursive function and the other is iterative. How could I compare the efficiency between them?


RECURSIVE

inorder(node)
  if node.left  ≠ null then inorder(node.left)
  print node.value
  if node.right ≠ null then

ITERATIVE

inorder(node)
  while hasleftchild(node) do
    node = node.left
  do
    visit(node)
    if (hasrightchild(node)) then
      node = node.right
      while hasleftchild(node) do
        node = node.left
    else
      while node.parent ≠ null and node == node.parent.right do
        node = node.parent
      node = node.parent
  while node ≠ null
3
Contributors
2
Replies
4
Views
6 Years
Discussion Span
Last Post by abhimanipal
0

> How could I compare the efficiency between them?
Use a profiler.

In big-O terms, the algorithm is the same, so the complexity is the same.

Generally speaking, iterative solutions tend to be more efficient, but you also have to write more code to make it work.

Simple recursive functions (and a smart compiler) may turn out to be iterative for free.
http://en.wikipedia.org/wiki/Tail_call

0

Put a start time and end time before the start and end of the function. You should start seeing differences in speed of execution after the number of nodes in the tree cross a certain threshold.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.