What is a binary search tree?

A Binary Search Tree (BST) is a special type of binary data tree where each node contains a key (value), and the following property holds for each node:

• All keys in the left subtree are less than the key of the node.
• All keys in the right subtree are greater than the key of the node.
• The left and right subtrees are also binary search trees.

This property allows efficient operations of search, insertion, and deletion. In a balanced binary search tree, these operations are performed in O(log n) time, where n is the number of nodes in the tree. In the worst case (degenerate tree), the time can reach O(n), turning the tree into a linked list.

Example of a node:

class Node {
  constructor(value) {
    this.value = value; // Node key
    this.left = null;   // Reference to left child
    this.right = null;  // Reference to right child
  }
}

Main operations:

• Search: Starts from the root. If the sought value is less than the current node's key, move to the left subtree; if greater — to the right; if equal — found.
• Insertion: Similar to search, but when the appropriate place (null) is reached, a new node is created.
• Deletion: The most complex operation. Depends on the number of children of the node to be deleted (0, 1, or 2). When deleting a node with two children, it is usually replaced with the smallest element from the right subtree or the largest from the left.

Binary search trees are used to create dictionaries, sets, and for efficient data sorting (tree sort). To maintain balance and guarantee logarithmic operation time, self-balancing variants such as AVL trees or red-black trees are used.