Flatten a Tree Time Complexcity

#1

What is the time complexcity of below code for this Problem.

Code Link : https://ide.codingblocks.com/s/120055

#2

@ritik_gajjar Since you are simply doing a post order traversal to form a linked list, So time complexity would be same as that of a post order traversal that is O(n).

#3

but sir in this loop we are again visiting the left nodes to reach the tail of the left subtree.

while(temp->right != NULL)
temp = temp -> right;

Geek Solution : https://www.geeksforgeeks.org/flatten-a-binary-tree-into-linked-list/

#4

@ritik_gajjar As taught by Prateek Bhaiya in the lecture and according to his code, the flatten tree function is of O(n) since it is simply a post order traversal and we are not revisiting any node.
But for your code since you are visiting nodes again…it may reach a worst case complexity of O(n^2) in case of skew tree.

1 Like
#5

yes Prateek bhaiya’s solution is better i am just thinking for all the solution.
Thank you bhaiya.

#6

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.

#7

Hello Bhaiya I found this.

It will be O(n) by master theorem.

1 Like
#8

Yes in the average case it would be O(n)

#9

Thank you very much.