for the time complexity of this code firstly i need to find out the complexity taken to calculate the height of the tree and after print all the levels? Right
Time complexity
Its O(n*H), as finding height takes O(n), then traversing tree for every level takes O(n).
In skewed tree H=n, so worst case complexity can be O(n^2).
@mayankA47 I actually I try to solve the height first which is O(n) but using recurrence relation i am get O(2^N):
I made the relation like that t(n) = 2t(n-1) + 1 ,
t(n-1) --> root-left, t(n-1) --> root->right and 1 for return statement i getting O(2^n)
Share your code for same!
This is incorrect! if total number of nodes are n, then how can you divide n-1 and n-1 to both right and left subtree?
It’s O(n) as you visit each node once.
BTW you used which digital writing instrument? if possible share details/link.
@mayankA47 I thought like that tere is one node at root and and we visted to the children so go one steps down for both so n-1 , n-1 like that?
I am using the onenote win 10 tools It required the mail address to share the link
No, according to this total left are n-1. so T(left) + T(right) = n-1.
Just dry run, or make a large tree (nodes=50), you can still find the height(had it been exponential, it would give TLE)
Ok I wanted to know which hardware?
@mayankA47 
I need to think like that or one node atmost can 2 child !>2 right for the tree property ?
Is this correct!!!
Yes and this is also valid even if tree is skewed!
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.