design with binary search tree


  • 0
    J

    This design is meant to scale. for integer as range is small, use list and set can fit the design well.

    class TreeNode {
    int low;
    int high;
    }

    as system scale up, the number may be too large.

    we can use a binary tree to track all "free" phone numbers.

    each tree node is a range, with low and high. all nodes do not overlap. the tree is constructed as binary search tree.

    so when you call get(), find any node in the "free" tree, return node.low, and adjust node.low. if low > high, delete the node. if it's connected with the range of the parent, merge with parent.

    similar handling for release(x).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.