[Javascript] AVL Tree
Solution: AVL Tree\n\nUse an AVL tree to find the number of greater elements in O(log(n)) time complexity.\n\nNote: The AVL Tree is implemented from scratch sin
**Solution: AVL Tree**\n\nUse an AVL tree to find the number of greater elements in `O(log(n))` time complexity.\n\nNote: The AVL Tree is implemented from scratch since JS doesn\'t have a built-in self balancing BST.\n\nTime Complexity: `O(n log(n))`\nSpace Complexity: `O(n)`\n```\nvar resultArray = function(nums) {\n  let n = nums.length, left = new AVLTree(), right = new AVLTree();\n  let arr1 = [nums[0]], arr2 = [nums[1]];\n  left.insert(nums[0]), right.insert(nums[1]);\n  for (let i = 2; i < n; i++) {\n    let greaterLeft = left.countGreater(nums[i]);\n    let greaterRight = right.countGreater(nums[i]);\n    if (greaterLeft > greaterRight) {\n      left.insert(nums[i]);\n      arr1.push(nums[i]);\n    } else if (greaterRight > greaterLeft) {\n      right.insert(nums[i]);\n      arr2.push(nums[i]);\n    } else {\n      if (left.getSize() <= right.getSize()) {\n        left.insert(nums[i]);\n        arr1.push(nums[i]);\n      } else {\n        right.insert(nums[i]);\n        arr2.push(nums[i]);\n      }\n    }\n  }\n  return [...arr1, ...arr2];\n};\n\nclass AVLTreeNode {\n  constructor(val) {\n    this.val = val;\n    this.left = null;\n    this.right = null;\n    this.height = 1;\n    this.size = 1; // number of nodes in tree rooted at this node\n  }\n}\n\nclass AVLTree {\n  constructor() {\n    this.root = null;\n  }\n  search(val, node = this.root) {\n    if (!node) return null;\n    if (node.val === val) return node;\n    if (val < node.val) {\n      return this.search(val, node.left);\n    } else {\n      return this.search(val, node.right);\n    }\n  }\n  insert(val) {\n    return this.root = this._insert(val, this.root);\n  }\n  _insert(val, node) {\n    if (!node) return new AVLTreeNode(val);\n    if (val < node.val) {\n      node.left = this._insert(val, node.left);\n    } else {\n      node.right = this._insert(val, node.right);\n    }\n    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));\n    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);\n\n    return this._rebalance(node);\n  }\n  remove(val, node = this.root) {\n    // To ensure we don\'t delete all occurances of `val`, pass in the reference of one occurance.\n    // To delete all nodes with value `val`, remove the check for `nodeToRemove` in _remove.\n    const nodeToRemove = this.search(val, node);\n    return this.root = this._remove(val, nodeToRemove, node);\n  }\n  // Four scenarios for deletion:\n    // 1. node to delete has no children - just delete it\n    // 2. node to delete only has a left child - replace it with the left child\n    // 3. node to delete only has a right child - replace it with the right child\n    // 4. node to delete has both left and right children - replace it with the next smallest node that is larger (use in order traversal to find the leftmost node in the right child)\n  _remove(val, nodeToRemove, node) {\n    if (!node) return null;\n    if (val < node.val) {\n      node.left = this._remove(val, nodeToRemove, node.left);\n    } else if (val > node.val) {\n      node.right = this._remove(val, nodeToRemove, node.right);\n    } else if (val === node.val && node === nodeToRemove) {\n      if (!node.left && !node.right) return null;\n      if (!node.right) return node.left;\n      if (!node.left) return node.right;\n\n      // has both left and right children\n      // inorder traversal on the right child to get the leftmost node\n      // replace the node value with the leftmost node value and remove the leftmost node from the right subtree\n      const leftmostNode = this._getLeftmost(node.right);\n      node.val = leftmostNode.val;\n\n      node.right = this._remove(leftmostNode.val, this.search(leftmostNode.val, node.right), node.right);\n    } else {\n      return node;\n    }\n    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));\n    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);\n\n    return this._rebalance(node);\n  }\n  countGreater(val, node = this.root) {\n    if (!node) return 0;\n\n    if (node.val > val) {\n      return 1 + this.getSize(node.right) + this.countGreater(val, node.left);\n    } else {\n      return this.countGreater(val, node.right);\n    }\n  }\n  _getLeftmost(node) {\n    while (node.left) {\n      node = node.left;\n    }\n    return node;\n  }\n  _getHeight(node = this.root) {\n    return node ? node.height : 0;\n  }\n  getSize(node = this.root) {\n    return node ? node.size : 0;\n  }\n  _getBalance(node = this.root) {\n    return node ? this._getHeight(node.left) - this._getHeight(node.right) : 0;\n  }\n  _leftRotation(node) { \n    let rightNode = node.right;\n    let rightNodeLeftChild = rightNode.left;\n    rightNode.left = node;\n    node.right = rightNodeLeftChild;\n\n    // node is now below rightNode and needs to be updated first\n    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));\n    rightNode.height = 1 + Math.max(this._getHeight(rightNode.left), this._getHeight(rightNode.right));\n\n    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);\n    rightNode.size = 1 + this.getSize(rightNode.left) + this.getSize(rightNode.right);\n\n    return rightNode; // right node is the new root\n  }\n  _rightRotation(node) {\n    let leftNode = node.left;\n    let leftNodeRightChild = leftNode.right;\n    leftNode.right = node;\n    node.left = leftNodeRightChild;\n\n    // node is now below leftNode and needs to be updated first\n    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));\n    leftNode.height = 1 + Math.max(this._getHeight(leftNode.left), this._getHeight(leftNode.right));\n\n    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);\n    leftNode.size = 1 + this.getSize(leftNode.left) + this.getSize(leftNode.right);\n\n    return leftNode; // left node is the new root\n  }\n  _rebalance(node) {\n    const balance = this._getBalance(node);\n    if (balance > 1 && this._getBalance(node.left) >= 0) { // left left\n      return this._rightRotation(node);\n    } else if (balance > 1 && this._getBalance(node.left) < 0) { // left right\n      node.left = this._leftRotation(node.left);\n      return this._rightRotation(node);\n    } else if (balance < -1 && this._getBalance(node.right) <= 0) { // right right\n      return this._leftRotation(node);\n    } else if (balance < -1 && this._getBalance(node.right) > 0) { // right left\n      node.right = this._rightRotation(node.right);\n      return this._leftRotation(node);\n    }\n    return node;\n  }\n}\n```
['JavaScript']