AVL Tree for storing obstacles with a baked-in singly linked list for increasing segment sizes.
Intuition\nYou want to keep track of obstacles in a binary search tree for fast insertion of new obstacles. \n\nFor the lookups, I linked every node in my tree 
# Intuition\nYou want to keep track of obstacles in a binary search tree for fast insertion of new obstacles. \n\nFor the lookups, I linked every node in my tree to the next node in the tree of a segment with a larger unobstructed space. Lookups then just entail a walk along this singly linked list of inceasing segment sizes, until you find a segment larger than you query size, or you surpass the query position \'x\'.\n\n# Approach\nI used a self balancing AVL tree as my binary search tree, to keep the complexity of insertion to a minimum.\n\nThe trickier part is keeping track for every node what the next node in the tree is with a larger segment space. This requires a lazy solution, where sometimes the next node with the \'largest\' segment space has gone stale because it shrunk in size. Solving this is as easy as cutting the necessary node out of the singly linked list, until the next segment is once again larger.\n\n# Complexity\n- Time complexity:\n    Insertion into the AVL tree is $$O(log(n))$$. The lookups in a singly linked list of segments are $$O(n)$$.\n\n- Space complexity:\n    There is one node in the tree for every obstacle, so space complexity is $$O(n)$$.\n\n# Code\n```\nint max(int a, int b) { return (a > b) ? a : b; }\n\nstruct Node {\n    int value;\n    struct Node* left;\n    struct Node* right;\n    struct Node* next;\n    struct Node* nextLargest;\n    int height;\n};\n\nstruct Node* newNode(int value) {\n    struct Node* node = (struct Node*)malloc(sizeof(struct Node));\n    node->value = value;\n    node->left = NULL;\n    node->right = NULL;\n    node->next = NULL;\n    node->nextLargest = NULL;\n    node->height = 1;\n    return (node);\n}\n\nint height(struct Node* N) {\n    if (N == NULL)\n        return 0;\n    return N->height;\n}\n\nint size(struct Node* node) {\n    if (node == NULL) {\n        return 0;\n    }\n\n    return (node->next ? node->next->value : INT_MAX) - node->value;\n}\n\nstruct Node* nextLargest(struct Node* node) {\n    int nodeSize = size(node);\n\n    struct Node* nextLargest = node->nextLargest;\n\n    while (nextLargest && size(nextLargest) <= nodeSize) {\n        nextLargest = nextLargest->nextLargest;\n        node->nextLargest = nextLargest;\n    }\n\n    return nextLargest;\n}\n\n// Necessary functions to maintain an AVL-tree\n\nstruct Node* rightRotate(struct Node* y) {\n    struct Node* x = y->left;\n    struct Node* T2 = x->right;\n\n    x->right = y;\n    y->left = T2;\n\n    y->height = max(height(y->left), height(y->right)) + 1;\n    x->height = max(height(x->left), height(x->right)) + 1;\n\n    return x;\n}\n\nstruct Node* leftRotate(struct Node* x) {\n    struct Node* y = x->right;\n    struct Node* T2 = y->left;\n\n    y->left = x;\n    x->right = T2;\n\n    x->height = max(height(x->left), height(x->right)) + 1;\n    y->height = max(height(y->left), height(y->right)) + 1;\n\n    return y;\n}\n\nint getBalance(struct Node* node) {\n    if (node == NULL)\n        return 0;\n    return height(node->left) - height(node->right);\n}\n\n// insertion function\n\nstruct Node* insertLeftLeaf(struct Node* node, struct Node* leaf) {\n    if (node == NULL)\n        return leaf;\n\n    node->left = insertLeftLeaf(node->left, leaf);\n    node->height = 1 + max(height(node->left), height(node->right));\n\n    // the balance here is always negative, since we inserted a leaf in the\n    // right node\n    int balance = getBalance(node);\n\n    if (balance > 1)\n        return rightRotate(node);\n\n    return node;\n}\n\nstruct Node* findNextLargerThan(struct Node* node, int size) {\n    if (node == NULL) {\n        return NULL;\n    }\n\n    struct Node* next = node->next;\n\n    while (next) {\n        if (next->value - node->value > size) {\n            return node;\n        }\n\n        node = nextLargest(node);\n        next = node ? node->next : NULL;\n    }\n\n    return node;\n}\n\nstruct Node* insertNode(struct Node* node, int value) {\n    if (node == NULL) {\n        return newNode(value);\n    }\n\n    if (value < node->value) {\n        node->left = insertNode(node->left, value);\n\n        if (!node->left->next) {\n            node->left->next = node;\n        }\n    } else if (node->next && value > node->next->value) {\n        node->right = insertNode(node->right, value);\n\n        if (!node->next) {\n            node->next = node->right;\n        }\n    } else {\n        // insert new node in \'next\' singly linked list\n        struct Node* leftLeaf = newNode(value);\n        leftLeaf->next = node->next;\n        node->next = leftLeaf;\n        node->right = insertLeftLeaf(node->right, leftLeaf);\n\n        if (!leftLeaf->next) {\n            node->nextLargest = leftLeaf;\n        } else {\n            int s1 = leftLeaf->value - node->value;\n            int s2 = leftLeaf->next->value - leftLeaf->value;\n\n            leftLeaf->nextLargest = findNextLargerThan(leftLeaf->next, s2);\n\n            if (s1 < s2) {\n                node->nextLargest = leftLeaf;\n            } else {\n                node->nextLargest =\n                    findNextLargerThan(leftLeaf->nextLargest, s1);\n            }\n        }\n    }\n\n    node->height = 1 + max(height(node->left), height(node->right));\n\n    int balance = getBalance(node);\n\n    if (balance > 1 && value < node->left->value)\n        return rightRotate(node);\n\n    if (balance < -1 && value > node->right->value)\n        return leftRotate(node);\n\n    if (balance > 1 && value > node->left->value) {\n        node->left = leftRotate(node->left);\n        return rightRotate(node);\n    }\n\n    if (balance < -1 && value < node->right->value) {\n        node->right = rightRotate(node->right);\n        return leftRotate(node);\n    }\n\n    return node;\n}\n\nbool sizeQuery(struct Node* leftNode, int value, int nodeSize) {\n    if (leftNode == NULL) {\n        return value >= nodeSize;\n    }\n\n    struct Node* node = leftNode;\n    int currentSize = size(node);\n\n    while (node && node->value + currentSize < value) {\n        if (nodeSize <= currentSize) {\n            return true;\n        }\n\n        node = nextLargest(node);\n        currentSize = size(node);\n    }\n\n    return nodeSize <= value - node->value;\n}\n\nint calcActualReturnSize(int** queries, int queriesSize) {\n    int returnSize = 0;\n\n    for (int i = 0; i < queriesSize; i++) {\n        if (queries[i][0] == 2) {\n            returnSize++;\n        }\n    }\n\n    return returnSize;\n}\n\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\nbool* getResults(int** queries, int queriesSize, int* queriesColSize,\n                 int* returnSize) {\n    *returnSize = calcActualReturnSize(queries, queriesSize);\n\n    bool* results = malloc(*returnSize * sizeof(bool));\n    int resultsIdx = 0;\n\n    struct Node* root = newNode(0);\n    struct Node* leftNode = root; // first obstacle\n\n    for (int i = 0; i < queriesSize; i++) {\n        // insert obstacle\n        if (queries[i][0] == 1) {\n            root = insertNode(root, queries[i][1]);\n\n            if (!leftNode) {\n                leftNode = root;\n            } else if (leftNode->left) {\n                leftNode = leftNode->left;\n            }\n        }\n\n        // size query\n        else {\n            bool result = sizeQuery(leftNode, queries[i][1], queries[i][2]);\n            results[resultsIdx] = result;\n            resultsIdx++;\n        }\n    }\n\n    return results;\n}\n```
['Binary Search Tree', 'C']