BST is another very interesting data structure. It allows for fast lookup, insertion and removal in expected O(log n) time. What’s even more important, BST keeps the data sorted and supports interval retrieval in time O(k+log n) for k items. That makes binary trees a key tool in…