void inorder(Node *root){
if(root!=NULL){
inorder(root->left);
cout<<root->key<<" ";
inorder(root->right);
}
I want to know how is inorder traversal of binary tree is O(n) mathematically? Shouldn't it be T(N) = 2*T(n-1) + const. ?
Asked
Active
Viewed 20 times
1
Shubham Sharma
- 141
- 1
- 9
-
1`2*O(n-1) + const` is `O(n)` – Aykhan Hagverdili May 07 '21 at 06:38
-
Recursive function doesn't work like this. if the function would beT(n) = T(n-1) then the time complexity would be O(n). But here T(N) = 2*T(n-1) + const. which implies time complexity to be O(2^n). – Shubham Sharma May 08 '21 at 07:23