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?

figure 13,2

Here is a snapshot of the original question.

My answer:

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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Jul 1, 2022 at 7:45
  • $\begingroup$ @Nathaniel I reviewed the question. The question is on the left tree only. $\endgroup$
    – Esha
    Jul 1, 2022 at 9:49
  • 3
    $\begingroup$ 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. $\endgroup$
    – Russel
    Jul 1, 2022 at 17:38
  • $\begingroup$ @Russel Thanks. Now I get it. Anyway, can you check my answer if the question were the wrong one only? $\endgroup$
    – Esha
    Jul 1, 2022 at 19:26
  • 2
    $\begingroup$ @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. $\endgroup$
    – Russel
    Jul 2, 2022 at 2:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.