How should I practice Balance a Binary Search Tree In Place?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Balance a Binary Search Tree In Place associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Balance a Binary Search Tree In Place

Google● HardNEW GRADPHONE SCREEN

Learn

Problem statement

Given the root of a binary search tree with distinct values, rebalance it in place using O(1) auxiliary space and return the new root.

Preserve every existing node and the in-order key sequence. Do not allocate an array, list, recursive call stack, or replacement tree nodes. One temporary sentinel node and a constant number of pointers are allowed.

Use the deterministic Day-Stout-Warren schedule: first rotate the tree into a sorted right vine. Let n be its node count, p the largest power of two at most n + 1, and leaves = n + 1 - p. Compress the first leaves vine links with left rotations, set n = n - leaves, then repeatedly set n = floor(n / 2) and compress that many links while n > 1. Return the sentinel's right child.

Function

balanceBstInPlace(root: TreeNode) → TreeNode

Examples

Example 1

root = [1,null,2,null,3,null,4,null,5]return = [4,2,5,1,3]

The DSW compression schedule turns the five-node right vine into a balanced tree rooted at 4.

Example 2

root = [5,4,null,3,null,2,null,1]return = [4,2,5,1,3]

Right rotations first convert the left chain into the same sorted vine.

Example 3

root = [4,2,6,1,3,5,7]return = [4,2,6,1,3,5,7]

The deterministic schedule reproduces this already perfect seven-node tree.

Constraints

The tree contains from 0 to 50000 nodes.
-10^9 <= node.val <= 10^9.
All node values are distinct and the input satisfies the binary-search-tree invariant.