Oh, I am wrong. I see that. The time complexity is still O(n). If we consider the while loop separately, the total time spent in while loop is n / 2 + n / 4 + ... + 1 = O(n). Besides the while loop, it takes O(n) to visit each node and do the modification of children stuff. Thus, the total time complexity is O(n).