# How does depths of nodes change after left-rotation in a BST (Exercise question from Cormen)

Let a,b,c be arbitrary nodes in the subtrees $$\alpha$$, $$\beta$$, $$\gamma$$, respectively, in the left tree of Figure 13.2 (that is given below). How do the depths of a,b,c change when a left rotation is performed on node x in the figure? Here is a snapshot of the original question.

Since in the left tree, left rotation is performed on node x and node y is above x, so subtree $$\gamma$$ will have not be affected by the rotation, and so depth of c remains the same.
Now, since subtree $$\beta$$ goes up by one level, so, depth of b decreases by 1 and since subtree $$\alpha$$ goes down by one level so depth of a increases by 1.

But I checked the answer online and they say:

The depth of c decreases by one, the depth of b stays the same, and the depth of a increases by 1.

The online answer is correct if I do right-rotation of the left tree at node y.

Am I misunderstanding something? Please review my answer and correct me if I am wrong.

• Please review your question: in the figure, the LEFT rotation is done on the tree on the RIGHT, not on the tree on the left. Jul 1, 2022 at 7:45
• @Nathaniel I reviewed the question. The question is on the left tree only.
– Esha
Jul 1, 2022 at 9:49
• Your issue appears to be an error in the book, check it here. Interestingly, this might be an error that started even in the first edition, see page 10 of this pdf and look at the correction for Exercise 14.2-4. Upon looking at the 4th edition, it was already corrected. Jul 1, 2022 at 17:38
• @Russel Thanks. Now I get it. Anyway, can you check my answer if the question were the wrong one only?
– Esha
Jul 1, 2022 at 19:26
• @Esha with your assumption, you are right with the changes in the depth of $a$ and $c$. As for $b$, it's not clear, since $b$'s depth will decrease only if it is in the right subtree of $\beta$. Otherwise, its depth stays the same. Jul 2, 2022 at 2:39