Trees (Binary Search Tree)

A binary search tree (BST) is a node-based binary tree data structure which has the following properties: the left subtree of a node contains only nodes with keys lesser than the node's key; the right subtree of a node contains only nodes with keys greater than the node's key; and both the left and right subtrees must also be binary search trees. This ordering property is the key to the BST's efficiency. Operations like searching for a value, inserting a new value, and deleting a value can be performed in O(log n) time on average for a balanced tree, where n is the number of nodes. The implementation is similar to a linked list in that you have a `Node` structure, but this time each node contains data, a pointer to a left child, and a pointer to a right child. The `BST` class would manage a pointer to the `root` node. The insertion and search operations are typically implemented recursively. To search for a value, you start at the root. If the value is less than the current node's key, you go to the left child; if it's greater, you go to the right child. You repeat this until you find the value or reach a `nullptr`, meaning the value is not in the tree. Tree traversal algorithms like in-order, pre-order, and post-order are also fundamental operations, often implemented recursively, to visit all the nodes in a specific order.