I found the following python code for inorder traversal of a binary search tree, with an explanation that its time complexity is O(n), where n is the number of nodes in the tree. I understand that the code visits every node in the tree, so its time complexity is linear in the number of nodes, but at each level of recursion, isn't it also performing an addition operation on lists that should take O(n) time? Shouldn't the time complexity be O(n^2)?
def inorder(r):
return inorder(r.left) + [r.val] + inorder(r.right) if r else []
Yes. List concatenation in Python seems to be an O(m + n) operation, as values are copied each time. Therefore, the work per node is not constant but depends on the length of its children. So you are correct in your thinking and this code is not O(n). However, it could easily be implemented in such a way that it would be O(n).
The worst-case complexity of this code would indeed be O(n^2), as you claim. It is easiest to think of the extreme case if the tree is so unbalanced that it is just a 1D linked list. Then, you would obtain a complexity of O(1 + 2 + ... + n) = O(n^2).