Binary Search Tree (BST)

A Binary Search Tree (BST) is a type of binary tree where each node has the following properties:

1. Key Value Property:
   • For any node N:
     • All values in the left subtree of N are less than the value of N.
     • All values in the right subtree of N are greater than the value of N.
2. No Duplicates:
   • Each value in the BST is unique.

Characteristics of BST

1. Binary Structure: Each node can have at most two children: left and right.
2. Sorted Order: An in-order traversal of a BST results in values being sorted in ascending order.
3. Efficient Search: BST allows for fast searching, insertion, and deletion operations, with time complexity $O(h)$, where $h$ is the height of the tree.

Basic Operations in BST

1. Search

To search for a value in a BST:

• Start at the root.
• Compare the value with the current node:
  • If it matches, the search is successful.
  • If it’s smaller, move to the left child.
  • If it’s larger, move to the right child.

Algorithm:

2. Insertion

To insert a value into a BST:

• Start at the root and traverse to the appropriate leaf position based on the key value property.
• Insert the new value as a leaf node.

Algorithm:

3. Deletion

To delete a node:

• Locate the node to be deleted.
• Handle three cases:
  1. No Children: Remove the node.
  2. One Child: Replace the node with its child.
  3. Two Children: Replace the node with its in-order successor or predecessor.

Algorithm:

Advantages of BST

1. Efficient Searches: Allows $O(h)$ search, where $h$ is the tree height.
2. Dynamic: BST can grow dynamically with insertions and deletions.
3. In-Order Traversal: Provides sorted data effortlessly.

Limitations

1. Unbalanced Trees: If the tree becomes skewed (e.g., inserting sorted data), operations can degrade to $O(n)$.
2. Height Dependency: Efficiency depends on the tree height.

Applications of BST

1. Search Operations: Fast retrieval of data in dictionaries, phonebooks, and databases.
2. Sorting: Use in-order traversal to retrieve sorted data.
3. Range Queries: Efficiently find all values within a range.

Example Tree

For the values: [50, 30, 70, 20, 40, 60, 80]

• Structure:

A Binary Search Tree is a fundamental data structure that provides efficient data organization for many computational problems.