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].

CodePudding user response：

I'll assume you are referring to this recursive Fibonacci algorithm, which takes as input a number