This structure allows for insertions in constant time but takes away our ability to apply a binary search, which brings our search time complexity back down to linear time.Now that we have gone over the possibilities, the data structure that most closely meets our needs is the sorted array, so how can we solve its insertion problem?.A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes..Each child must either be a leaf node or the root of another binary search tree..The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.The binary search tree provides us with some interesting time complexities..Therefore, searching in a binary search tree has a worst-case complexity of O(n)..The height for a balanced binary tree will be log N therefore the time complexity for its basic operations will also be O(log N).Now the only question left to answer is how to keep our trees balanced..This guarantees that lookup, insertion, and deletion all take O(log N) time in both the average and worst cases.To able to keep our AVL tree balanced we must keep track of the height difference between 2 children..Notice that this formula should never produce anything above 2 since we would only be adding one node at a time to an already balanced tree..However, there is one instance where an insertion creates a zig-zag pattern, where a single rotation does not change the final balance of the tree..Inserting a new node into our AVL tree can be done in O(log N) time and searching can be done with the same complexity.I hope this helps to shine a light into binary search trees and their strengths.. More details