I am right now working with a Binary Search tree. I wonder what is the Tim complexity for a Binary Search tree. More Specific what is the worst case Time complexity for the operation height, leaves and toString for a Binary Search tree and why?
>Solution :
All three operations have a O(n) worst-case time complexity.
For height: all nodes will be visited when the tree is degenerate, and all nodes except one have exactly one child.
For leaves: each node will have to be visited in order to check whether they are a leave.
For toString: obviously all nodes need to be visited.