FastPrepImplement a Self-Balancing BST (AVL Tree)

Implement a Self-Balancing BST (AVL Tree)

Microsoft logoMicrosoft● HardINTERNONSITE INTERVIEW

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. contains 25 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.
  • contains 40 reports [0]. The final preorder is [20, 10, 5, 50, 30, 70].

Constraints

  • 1 <= operations.length <= 10^4
  • values.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^5 numbers.

More Microsoft Onsite Interview questions

Similar questions at other companies

Interview reports that mention this question

Microsoft interview experiences

All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[][] runAvlTree(String[] operations, int[] values) {
        // Write your code here.
    }
}
Checking account…