(Java) Problem 10.15

**daemoohn** · February 10, 2016, 11:37pm

Hi there. I think the complexities presented in the book might be wrong.
The space complexity for the count field (the number of nodes in subtree that are locked) is O(1). For the entire tree is probably O(n).
The time complexity to check if a node is already locked is O(1), it’s just a field in the node, it shouldn’t be O(h).

**adnanaziz** · February 12, 2016, 4:38pm

You are correct, I have updated the text to state that checking if a node is locked to O(1), don’t know how that slipped through for so long. I also clarified that the O(n) refers to the additional space complexity for the entire tree.

Thanks for taking the trouble to let us know that, we really appreciate it,

bye,
Adnan