For the in place solution, given the nested while loop, in the worst case senario, won’t the time complexity be O(n**2) instead of O(n)?
Hello @wangyuhong,
I would like to clarify that the time complexity of this solution is indeed O(n), not O(n^2). The nested while loop, which traverses the left subtree to find the rightmost node, contributes to a linear-time complexity.
The reason behind this is that each node in the tree is processed only once during the traversal. The nested while loop, while it may seem like it introduces an additional factor, is constrained by the fact that it traverses each right child at most twice: once during the original traversal and once during the linking process.
I hope this clarifies your confusion regarding the time complexity of the coded solution. Feel free to share any more feedbacks and suggestions. Thanks!
Happy learning!