How in the recursive method for level order printing the time complexity is O(N^2)? Sir explained it in the recursive video but the explanation seems more like of an iterative way. Please help.
CPP - Binary Tree BFS Traversal-I
O(N^2) is basically the worst case complexity, as in case of skewed tree, the total height of tree is O(N), and since you are traversing complete tree, it will take further O(N), and hence it is O(N^2).
But ma’am in the recursive code of the height calculation, at every node there are two possibilities that whether to go to right or left. So going from the root to the base case should take 2N steps and finally for going away from the base case (top to down) should take 2N more steps. Finally the complexity should be of O(4*N). Tell me where I am gone wrong?
See, for calculating height, the time complexity is O(N), in case of recursive solution only, since you will traverse through every node, and then at every level, the complexity will be like this
O(1) + O(2) + … O(N)
hence it will be O(N^2) only.