Events arrive at a timeline widget in arbitrary order, often already sorted. To keep lookups fast, it stores their timestamps in an AVL tree: a binary search tree that rotates after each insert so every node's two subtree heights differ by at most 1.
Write buildIndex(values) that inserts the values one by one, in order, into an initially empty AVL tree and returns the root. Use the standard rules so the result is unique: values smaller than a node go left, others (including equal values) go right; after each insert, walking back up, fix the lowest unbalanced node with a single rotation (left-left or right-right case) or a double rotation (left-right or right-left case).
Input: values = [1,2,3,4,5,6,7] Output: [4,2,6,1,3,5,7]
Sorted input would make a chain in a plain search tree; rotations keep it perfectly balanced.
Input: values = [30,10,20] Output: [20,10,30]
Inserting 20 creates a left-right case at 30: rotate 10 left, then 30 right.
0 <= values.length <= 2000-10^5 <= values[i] <= 10^5Trees are written level by level, like [1, 2, 3, null, 4], where null is a missing child. Your function works with TreeNode objects, each with val, left, and right.
Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #376 Build a Self-Balancing Index. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.