A notebook contains a binary search tree data structure which in its present version is limited to a few very basic features. In particular, searching for an element and inserting an element into the tree are implemented, whereas deletion is missing. Each node (i.e., self, with the value self._item stored in the root node) is linked by object references to two other nodes:
Extend this implementation by a method delete(self, value) that deletes one occurrence of value from the tree that has self as its root node, if one or multiple such occurrences exist.
The binary search tree must remain sorted at all times; in particular, each node under which there are any subtrees (i.e., at least one out of _left and _right is distinct from None) must also store a data item (i.e., _item may not be None). All values stored in _left must be smaller than _item, and all values stored in _right must be greater than or equal to _item.
Submission deadline: 11th December 2021; discussion planned for 20th January 2022. Group work by up to four people is welcome.