What is a binary search tree?

A Binary Search Tree (BST) is a special kind of binary tree in which elements are arranged according to an ordering rule:

#Rule

For every node in the tree:

• all values in the left subtree are smaller than the node's value,
• all values in the right subtree are larger than the node's value.

#Example

Here:

• for 8, the left subtree {1,3,4,6,7} < 8,
• the right subtree {10,13,14} > 8.

#Main operations

• Search - O(h), where h is the height of the tree (O(log n) on average);
• Insertion - finds the correct place using the same rule and inserts the node;
• Deletion - requires carefully rebuilding the subtrees.

#Features

• Efficient when the tree is balanced (search in O(log n)).
• When unbalanced (for example, if data is inserted in increasing order), it turns into a list - complexity O(n).

#Summary

A Binary Search Tree is a structure that stores data as a tree with a strict ordering, which lets you search, add, and remove elements quickly compared to linear structures.