easy +10 pts

Binary Search Tree Class

Implement a minimal BST with insertion, search, and traversal via a sequence of operations.

Implement a function `binary_search_tree_sequence(operations: List[List]) -> List` that takes a list of operations to be performed on a single `BinarySearchTree` instance, and returns a list of results for each operation in the same order. Each operation is a list where the first element is the operation name, and optional following elements are arguments. - `['insert', value]` – insert an integer `value` into the BST. Duplicates are ignored. Returns `None`. - `['contains', target]` – return `True` if `target` is present, else `False`. - `['inorder']` – return a list of the tree's values in in-order (left, root, right) traversal order. You must also define a `BinarySearchTree` class with the following methods so that the sequence runner can use them: - `__init__(self)` – initializes an empty tree. - `insert(self, value: int) -> None` – inserts a new value, ignoring duplicates. - `contains(self, target: int) -> bool` – checks membership. - `inorder(self) -> List[int]` – returns in-order list. Your solution must not use any external libraries. All values are integers. The sequence runner should create a fresh `BinarySearchTree` for each call to `binary_search_tree_sequence`. For any operation that does not produce a result (insert), return `None` in the output list.

Constraints

Number of operations in a sequence is between 0 and 10^5. Values are integers between -(10^9) and 10^9. Operations should be efficient: average O(log n) per insert/contains, in-order traversal O(n).

Example

```python
binary_search_tree_sequence([
    ['insert', 5],
    ['insert', 3],
    ['insert', 7],
    ['insert', 3],
    ['contains', 3],
    ['contains', 4],
    ['inorder']
])
# Returns: [None, None, None, None, True, False, [3, 5, 7]]
```
10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Create a BinarySearchTree instance at the start of the sequence runner.
Iterate over operations, dispatch by the operation name, and collect the result (None for insert).
For insertion, recurse left if value < node.value, right if value >, and stop if equal.
In-order traversal: visit left subtree, then root, then right subtree.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.