Skip to content
Hello Python

Recognize Three-Node Tree Rotations

Practice ExerciseAdvancedMediumBalanced TreeBinary Search TreeTree

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement balance_three_nodes(insertion_order). insertion_order contains exactly three distinct comparable values. Return [root, left_child, right_child] for the balanced BST after the required single or double rotation.

Starter code

def balance_three_nodes(insertion_order):
    pass
Test cases

outer-cases

{
  "args": [
    [
      1,
      2,
      3
    ]
  ]
}

Expected: [2,1,3]

inner-left-right

{
  "args": [
    [
      3,
      1,
      2
    ]
  ]
}

Expected: [2,1,3]

Wizard outline
  1. Step 1: Rotate the right-right case

    Return the middle inserted value as root for an ascending three-node chain. The ascending case makes the median-root invariant visible without a double rotation.

  2. Step 2: Rotate the left-left case

    Handle a descending chain by promoting its middle value to the root. The descending case confirms that direction changes but the median-root invariant does not.

  3. Step 3: Normalize both zigzag cases

    Generalize all four rotation shapes by selecting minimum, median, and maximum. A zigzag needs a double rotation operationally, but its final three-node invariant is identical.

Footguns and prerequisites
  • A single rotation does not repair an inner left-right or right-left zigzag.
  • Rotating by insertion position without checking key order breaks BST ordering.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Express the post-rotation invariant directly: among three distinct keys, the median is the balanced root and the extrema are its children.

Why it works: Sorting identifies the unique median, minimum, and maximum. Placing them as root, left, and right satisfies BST order and gives both subtrees equal height for every outer or inner imbalance.

def balance_three_nodes(insertion_order):
    left, root, right = sorted(insertion_order)
    return [root, left, right]