A Binary Search Tree (BST) is a type of data structure that is used to organize and store data in a hierarchical manner. It is a variant of the general tree data structure and specifically falls under the category of binary trees, where each node has at most two children, typically referred to as the left child and the right child[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16].
Characteristics of Binary Search Trees
Node Structure: Each node in a BST contains a key (and possibly associated data), along with references to its left and right children[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16].
Ordered Structure: The key in any node is greater than the keys in all nodes in its left subtree and less than the keys in all nodes in its right subtree. This property must be true for every node in the tree[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16].
Dynamic Size: The size of a BST can grow or shrink dynamically as nodes are added or removed[3][4][5][6][7][8][9][10][11][12][13][14][15][16].
Efficient Operations: BSTs allow for efficient searching, insertion, and deletion of nodes. The average time complexity for these operations is $$O(\log n)$$, where $$n$$ is the number of nodes in the tree. However, in the worst case (such as when the tree becomes unbalanced), these operations can degrade to $$O(n)$$[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16].
Basic Operations
Search: To find a value, start at the root and compare it to the value you are looking for. If the value is less than the current node's key, move to the left child; if greater, move to the right child. Repeat this process until you find the value or exhaust the nodes[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16].
Insertion: To insert a new key, the same logic as search is applied to find the correct position to maintain the BST properties. Once the position is found, a new node with the given key is added as a leaf[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16].
