Bst

BST commonly refers to Binary Search Tree in computer science, a node-based data structure that stores items in a hierarchical, ordered form. Each node contains a key and may store an associated value, along with references to left and right children. The BST property requires that keys in the left subtree are strictly less than the node’s key, and keys in the right subtree are greater than or equal to the node’s key. This ordering enables efficient search, insertion, and deletion.

Search proceeds from the root by comparing the target key to the current node’s key and moving left or right accordingly. If the tree is balanced, these operations typically run in O(log n) time; in the worst case, a degenerate tree (like a chain) can incur O(n) time. Deletion is more complex: removing a node may require restructuring the subtree, often by replacing the node with its in-order successor or predecessor to preserve the BST property.

Common traversals include in-order (which yields keys in sorted order), pre-order, post-order, and level-order. In-order traversal is especially important for producing a sorted sequence from the BST.

BSTs are not self-balancing by default; their height can grow to the number of nodes, degrading performance. Variants that enforce balance include AVL trees and red-black trees, which maintain height within tight bounds to guarantee O(log n) worst-case time for operations. Other approaches include splay trees and treaps.

Applications include implementing dynamic sets and associative arrays, symbol tables, and in-memory representations of ordered data, where efficient ordered iteration and range queries are needed. BST terminology and variants also appear in many programming libraries.

BST may also refer to British Summer Time, the daylight saving time observed in the United Kingdom and parts of Europe.