BST

A binary search tree (BST) is a binary tree data structure in which each vertex has at most two children, referred to as the left and right child.
In a BST, the key values of vertices in the left subtree are less than the key value of the root, and the key values of nodes in the right subtree are greater than the key value of the root. This property allows for efficient search, insertion, and deletion operations, making BSTs useful for implementing algorithms such as binary search and various data structures like sets and maps.

BST implementation

Basic operations time complexity

Note

A balanced tree is a data structure in which the heights of the subtrees of any node differ by at most one. We will discuss it in more detail in the next sections.

1. Insertion:
   • Best and Average Case (O(log n)): In a balanced BST, insertion involves traversing down the tree from the root to find the appropriate position for the new node. At each level, the search space is divided in half, reducing the search time logarithmically with respect to the number of nodes;
   • Worst Case (O(n)): If the tree becomes unbalanced, such as when nodes are inserted in sorted order, the tree can degenerate into a linked list. In this case, the insertion operation becomes linear with respect to the number of nodes, as each new node is simply appended to the end of the list.
2. Deletion:
   • Best and Average Case (O(log n)): Similar to insertion, deletion in a balanced BST involves traversing down the tree to find the node to be deleted. The search space is divided in half at each level, resulting in a logarithmic time complexity;
   • Worst Case (O(n)): As with insertion, if the tree becomes unbalanced, deletion can degrade to O(n) time complexity. For example, deleting a node from a skewed tree may require traversing through most or all of the nodes.
3. Search:
   • Best and Average Case (O(log n)): The BST's structure allows for efficient search by recursively traversing down the tree from the root. The search space is halved at each level, leading to a logarithmic time complexity;
   • Worst Case (O(n)): In the worst case scenario, the tree is unbalanced, resulting in a linear search time. This occurs when the tree degenerates into a linked list, and the search traverses through most or all of the nodes.