JavaScript Binary Search Tree
This is not optimal since some inputs could result in O(room length * query length), but it\'s less complex than implementing a self-balancing binary search tre
This is not optimal since some inputs could result in O(room length * query length), but it\'s less complex than implementing a self-balancing binary search tree.\n\nThe general gameplan:\n- Sort both rooms and queries in decreasing order by size. This will allow us to search the minimum number of rooms for each query.\n- Since our output needs to be in the same order as the queries, map a new array to the queries\' indices and sort that array instead.\n- Create an output array, set default to -1\n- For each query\n  - If the requested size is greater than the largest room size, continue\n  - While the next room we need to add to the BST is >= the current requested size, add the room number to the BST.\n  - Then search the BST for the closest room id\n\n```\nvar closestRoom = function (rooms, queries) {\n  rooms.sort((a, b) => b[1] - a[1]);\n  const byRoomSize = queries\n    .map((_, i) => i)\n    .sort((a, b) => queries[b][1] - queries[a][1]);\n\n  const closest = new Array(queries.length).fill(-1);\n  const binarySearchTree = new BinarySearchTree();\n  let currentRoom = 0;\n  \n  byRoomSize.forEach((query) => {\n    const [preferredRoom, minimumSize] = queries[query];\n    if (rooms[0][1] < minimumSize) {\n      return;\n    }\n\n    while (currentRoom < rooms.length && rooms[currentRoom][1] >= minimumSize) {\n      binarySearchTree.add(rooms[currentRoom][0]);\n      currentRoom += 1;\n    }\n\n    closest[query] = binarySearchTree.search(preferredRoom);\n  });\n\n  return closest;\n};\n\nclass BinarySearchTree {\n  constructor() {\n    this.root = null;\n  }\n\n  add(room) {\n    this.root = this.insert(this.root, room);\n  }\n\n  insert(node = this.root, room) {\n    if (!node) return new TreeNode(room);\n\n    if (node.room < room) {\n      node.right = this.insert(node.right, room);\n    } else {\n      node.left = this.insert(node.left, room);\n    }\n\n    return node;\n  }\n\n  search(room, node = this.root) {\n    if (node.room === room) return room;\n\n    const currentDistance = Math.abs(node.room - room);\n    const nextChild = node.room < room ? node.right : node.left;\n\n    if (!nextChild) return node.room;\n\n    const closestChild = this.search(room, nextChild);\n    const childDistance = Math.abs(closestChild - room);\n\n    if (childDistance < currentDistance) return closestChild;\n    if (childDistance === currentDistance) return Math.min(closestChild, node.room);\n    return node.room;\n  }\n}\n\nclass TreeNode {\n  constructor(room) {\n    this.room = room;\n    this.left = null;\n    this.right = null;\n  }\n}\n```
['Binary Search Tree', 'JavaScript']