A binary search tree is a data structure that keeps items in sorted order.
The correct answer and explanation is:
Correct Answer:
A Binary Search Tree (BST) is a data structure that stores elements (typically numbers or keys) in a hierarchical tree structure, where each node has at most two children. For each node:
- The left child contains only nodes with values less than the parent node’s value.
- The right child contains only nodes with values greater than the parent node’s value.
Explanation (300 words):
A Binary Search Tree (BST) is a specialized form of a binary tree that maintains sorted order among its elements. It is widely used in computer science for searching, sorting, and organizing data efficiently.
In a BST, each node has three main parts: a value (key), a left child, and a right child. The key principle of BSTs is that for any given node:
- All values in the left subtree are smaller.
- All values in the right subtree are larger.
This property allows for efficient operations. Searching in a BST starts at the root and proceeds either left or right, depending on the value being sought. On average, this search takes O(log n) time, where n is the number of nodes, making it much faster than linear search in an unsorted list.
Insertion in a BST follows a similar path: we compare the new value with nodes from the root downward and place it as a new leaf where the correct position is found. Deletion is more complex and involves three cases:
- The node is a leaf – simply remove it.
- The node has one child – replace it with its child.
- The node has two children – replace it with its in-order successor (smallest value in the right subtree) or in-order predecessor (largest value in the left subtree).
A well-balanced BST keeps operations efficient. However, if elements are inserted in a sorted order without balancing (e.g., 1, 2, 3, 4…), the tree degenerates into a linked list, making operations O(n) in time complexity.
To overcome this, self-balancing BSTs like AVL trees or Red-Black trees are often used, ensuring that the tree remains balanced for consistently fast operations.
BSTs are foundational in algorithms, databases, and file systems due to their speed and efficiency.