The binary search tree (BST) is a data structure where nodes are arranged in a way that each one can have up to two children. Elements are arranged in such a way that a node’s “left” child contains a lesser element, and its “right” child contains a greater element. Thus, all elements to the left of a given node will be less than it, and all elements to the right will be greater (Tutorialspoint, n. d.). To find an element, the algorithm starts at the root node and examines the left child if the requested element is less or the right child if it is greater than the current node. If the next child node to be examined is empty, then the requested element is not in the tree. A BST’s insertion function performs the same search and adds the new node once it reaches this “dead end.”
Data in a BST is stored in sorted order and can be easily displayed in bottom-to-top order. Similarly, addition, retrieval, and deletion operations are generally performed in O(logN) time. However, since new elements are added by traversing the tree, adding elements that are already ordered will create a tree where elements have only one child. Such a tree is similar to a singly-linked list in terms of efficiency: the program may have to traverse all existing nodes while searching for an element, resulting in an O(N) speed. To compensate for this issue while still using a BST, the insertion order can be randomized. In summary, a BST is an efficient data structure that naturally sorts elements as they are inserted and allows quick access to arbitrary elements. However, if the data is added in a pre-sorted order or generated in a naturally ascending order (e. g., alphabetized list or incrementing order numbers), a different data structure, such as a hash table, may be preferable.
Reference
Tutorialspoint.com (n. d.). Data Structure – Binary Search Tree.