Left and right rotations

Intermediate Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

A right rotation around node y with left child x makes x the new root of the subtree and y the right child of x. It is symmetric for the other side.

Double rotations (left-right, right-left) combine two simple rotations when the imbalance is deeper.

Rotations preserve the search tree invariant and change the height.

Role	before	after
root of the pair	y	x
inner edge	y.left = x	x.right = y
## Where used

Local pointer updates in AVL/Red-Black and related structures. Rotations are the mechanism by which indices become flat again after Insert/Delete without rebuilding everything.

Depth

A rotation changes local parent-child relationships without destroying the ascending in-order sequence of the keys. The middle subtree switches sides while remaining between the same boundary keys.

In addition to child references, parent references, root reference, and stored heights may need to be updated. The order of assignments must retain all necessary old references.

A straightforward imbalance is fixed with a single rotation. For a bent path, a rotation at the child must be performed first, followed by a rotation at the affected node.

Difficulty levels

Check the key order before and after a rotation.
Update all affected references and metadata.
Recognize simple and double rotation cases.

Pitfalls

A correct local drawing is not sufficient if the new subtree root is not reconnected to its previous parent node. Heights should only be recalculated after the references are updated.

University approvals: 0

Tasks

Question 1

What remains preserved during a rotation in a search tree?

The exact height of each node

The in-order sequence of the keys

The HashCodes

The array capacity

Question 2

What property must a search tree rotation preserve?

The identity of the root

The search order of the keys (BST invariant)

The depth of each individual node

The number of null references per node

Question 3

Perform a classic right rotation at node y.

Hint

Store required TreeNode references in local variables. Child pointers are modified by assignments to .left and .right.

public class TreeRotations {
  public static class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int value) { this.value = value; }
  }
  public static TreeNode rotateRight(TreeNode y) {
    // TODO
    return null;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy