CODEWITHSUNDEEP
algorithmtree
prin
prin

Reputation: 35

Why is time complexity of binary tree traversal (like preorder) not exponential?

Why is time complexity of binary tree traversal (like preorder) not exponential? For example, in common implementation of Fibonacci sequence, it is exponential because for every instance, you call the Fibonacci function twice. So, how come it is O(n) for preorder traversal (where also the recursive function gets called twice) [I know it is O(n) as every nodes gets traversed, so please don't answer in terms of why it is O(n). Answer in comparison with the Fibonacci recursive implementation, as I want to see the difference].

Upvotes: 1

Views: 233

Answers (2)

trincot
trincot

Reputation: 350127

I'll assume you are referring to this recursive Fibonacci algorithm, which takes as input a number 𝑖, and returns the 𝑖th number from the Fibonacci sequence:

def fibonacci(number):
  if number < 2:
    return number
  else:
    return fibonacci(number - 1) + fibonacci(number - 2)

If we consider each distinct value of number (that is used for calls of this function) as a "node", then notice an important difference with the binary-tree-traversal problem:

This Fibonacci algorithm will visit the same node multiple times, and this gets worse as recursive calls are made on already visited "nodes". The recursion tree is not really a tree, but a directed acyclic graph. Here is the recursion tree for when calling Fibonacci(5):

enter image description here

So we see that Fibonacci(3) is calculated twice, each time doing the whole work of deeper recursion. So Fibonacci(2) and Fibonacci(0) are each called 3 times, and Fibonacci(1) 5 times. In total there are 15 "visits", including the duplicates.

This is not happening with the recursive tree-traversal algorithm, where the recursion tree really is a tree (that is equivalent to the tree being traversed).

This explains the difference in time complexity.

It also explains why this naive Fibonacci algorithm can be improved by avoiding the duplicate "node visits", so that it becomes O(n) too.

Upvotes: 2

Emil Vikstr&#246;m
Emil Vikstr&#246;m

Reputation: 91902

There are two ways of looking at it:

  1. For each node, you are making the recursive call exactly twice. This already tells you that it's a constant factor for each additional node, regardless of where in the tree this node is situated.

But just in case this is not enough for you there is the other viewpoint too:

  1. In each recursive call the sub-problem is halved. So you are doubling the amount of calls but halving the amount of work to be done.

Both of these cases differ from the "flawed fibonacci implementation" in that you are never visiting a node more than once. In the fibonacci example you are doing the same work over and over again.

Upvotes: 0

Related Questions