Implement a Self-Balancing BST (AVL Tree)
Updated
Problem statement
Implement an AVL tree, a binary search tree that rebalances itself after every change. The tree holds distinct integers and starts empty. For every node, smaller values are in its left subtree and larger values are in its right subtree.
The height of an empty subtree is 0, and the height of a node is 1 plus the larger height of its two subtrees. A node's balance is the height of its left subtree minus the height of its right subtree. After every insert or delete, every node must have a balance of -1, 0 or 1.
Process the calls in order. Call i is operations[i] with the value values[i]:
"insert": if the value is not in the tree, add it as a new leaf in its BST position. If it is already there, nothing changes."delete": if the value is in the tree, remove it. If its node has no children, remove the node. If it has one child, that child takes its place. If it has two children, copy the smallest value in its right subtree into it, then delete that value from the right subtree. If the value is not in the tree, nothing changes."contains": report[1]if the value is in the tree, otherwise[0]."preorder": report the values in preorder: the node, then its left subtree, then its right subtree. Report[]for an empty tree.values[i]is not used.
After an insert or delete, go back up from the changed spot to the root. At each node on the way, update its height. If its balance is 2, then: if its left child's balance is -1, rotate left at the left child first; then rotate right at the node. If its balance is -2, then: if its right child's balance is 1, rotate right at the right child first; then rotate left at the node. So a child with balance 0 always gets a single rotation.
Return a list with one entry for each "contains" or "preorder" call, in order. "insert" and "delete" calls add nothing to the result.
Function
runAvlTree(operations: String[], values: int[]) → int[][]Examples
Example 1
operations = ["insert","insert","insert","preorder"]values = [10,20,30,0]return = [[20,10,30]]- Inserting 10 and then 20 gives root 10 with right child 20.
- Inserting 30 puts it to the right of 20. Node 10 now has a left height of 0 and a right height of 2, so its balance is -2. Its right child 20 has balance -1, so one left rotation at 10 fixes it, and 20 becomes the root.
- The preorder (node, then left subtree, then right subtree) is
[20, 10, 30].
Example 2
operations = ["insert","insert","insert","insert","insert","insert","insert","contains","preorder"]values = [50,20,70,10,30,25,30,25,0]return = [[1],[30,20,10,25,50,70]]- After inserting 50, 20, 70, 10 and 30, the tree is balanced: root 50, left child 20 (children 10 and 30), right child 70.
- Inserting 25 puts it as the left child of 30. Walking back up, 30 has balance 1 and 20 has balance
1 - 2 = -1, which is fine, but 50 has left height 3 and right height 1, so its balance is 2. - The left child 20 leans right (balance -1), so this needs a double rotation: rotate left at 20, then rotate right at 50. Now 30 is the root, with left child 20 (children 10 and 25) and right child 50 (right child 70).
- Inserting 30 again changes nothing because 30 is already in the tree.
contains25 reports[1], and the preorder is[30, 20, 10, 25, 50, 70].
Example 3
operations = ["insert","insert","insert","insert","insert","insert","insert","insert","delete","preorder","delete","delete","contains","preorder"]values = [40,20,60,10,30,50,70,5,40,0,99,60,40,0]return = [[50,20,10,5,30,60,70],[0],[20,10,5,50,30,70]]- The eight inserts build root 40 with left subtree 20 (children 10 and 30, and 5 under 10) and right subtree 60 (children 50 and 70). No rotation is needed.
- Deleting 40, which has two children, copies in the smallest value of its right subtree, 50, and then deletes 50 from the right subtree. The tree stays balanced, and the preorder is
[50, 20, 10, 5, 30, 60, 70]. - Deleting 99 changes nothing because it is not in the tree.
- Deleting 60, which has one child, puts 70 in its place. Now the root 50 has left height 3 and right height 1, so its balance is 2. Its left child 20 has balance
2 - 1 = 1, so one right rotation at 50 fixes it, and 20 becomes the root. contains40 reports[0]. The final preorder is[20, 10, 5, 50, 30, 70].
Constraints
1 <= operations.length <= 10^4values.length == operations.length- Each
operations[i]is"insert","delete","contains"or"preorder". -10^9 <= values[i] <= 10^9- All returned lists together hold at most
10^5numbers.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- N-Ary Tree BFS CodecGoogle · ONSITE INTERVIEWGoogle interview questions
- Construct a Tree from Level-Order and Inorder TraversalsSalesforce · ONSITE INTERVIEWSalesforce interview questions
- N-Ary Tree Codec OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Binary Tree Maximum Path SumGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions
- Build a Tree from Preorder and Inorder TraversalsStackAdapt · ONSITE INTERVIEWStackAdapt interview questions
- Simplify a Binary Expression TreeAmazon · ONSITE INTERVIEW