[link](https://leetcode.com/problems/my-calendar-i/)

---

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

- MyCalendar() Initializes the calendar object.
- boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

#### Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

#### Constraints:

- 0 <= start < end <= 109
- At most 1000 calls will be made to book.

---

Node: The Node class represents a node in a binary search tree (BST) used to store booked events in the MyCalendar class. Each node contains information about the range it represents (start and end) and pointers to its left and right child nodes (left and right).

MyCalendar: The MyCalendar class uses a binary search tree (BST) to keep track of booked events. It allows users to book events by calling the book method, which internally updates the binary search tree using the update method.

Here's how the MyCalendar class works:

The constructor (__init__) initializes an empty binary search tree by setting the root to None.

The update method updates the binary search tree with a new event represented by the start and end parameters. It does this by recursively traversing the tree and checking if there is any overlap between the existing events and the new event. If there is no overlap, a new node is created and inserted into the appropriate position in the tree. If there is an overlap, the method returns False to indicate that the booking cannot be made.

The book method allows users to book events by calling the update method with the specified start and end parameters. If the booking is successful (i.e., no overlap with existing events), the method returns True; otherwise, it returns False.

#### Solution 1

class Node:
    def __init__(self, start, end):
        self.left = None
        self.right = None
        self.start = start
        self.end = end


class MyCalendar:

    def __init__(self):
        self.root = None

    def update(self, node, start, end):
        if not node:
            return Node(start, end), True

        if node.start <= start < node.end or node.start < end <= node.end or (start < node.start and end > node.end):
            return node, False

        if start < node.start:
            node.left, check = self.update(node.left, start, end)
        else:
            node.right, check = self.update(node.right, start, end)

        return node, check


    def book(self, start: int, end: int) -> bool:
        self.root, check = self.update(self.root, start, end)
        return check
        

The time complexity of the update method depends on the height of the binary search tree, which can be at most O(log n) for a balanced tree, where n is the number of booked events. However, in the worst case, the tree might be unbalanced, and the time complexity could be O(n).

The space complexity of the MyCalendar class is O(n), mainly due to the storage of the binary search tree nodes.