# Which Data Structure Is Used in BST?

//

Heather Bennett

When it comes to binary search trees (BST), the data structure used is, as the name suggests, a tree. Specifically, it is a binary tree. A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.

## What is a Binary Search Tree?

A binary search tree is a specific type of binary tree that has an ordering property. This means that for any given node in the tree, all elements in its left subtree are less than the node’s value, and all elements in its right subtree are greater than the node’s value. This ordering property allows for efficient searching, insertion, and deletion operations.

## Implementing a Binary Search Tree

To implement a binary search tree, we typically use nodes that contain both data and references to their left and right children. Each node represents an element or data point in the BST.

We can represent a node using classes or structures in programming languages such as C++, Java, or Python. Here’s an example of how a simple BST node can be represented using a Python class:

```class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
```

## Operations on Binary Search Trees

Binary search trees support several operations such as searching for an element, inserting a new element, and deleting an existing element. These operations take advantage of the ordering property of BSTs to efficiently navigate through the tree.

### Searching

The search operation in a BST starts at the root node and compares the Target value with the current node’s value. If they match, we have found our desired element.

If not, we move down either to the left or right child based on the comparison. This process continues until we find the element or reach a null (empty) node.

### Insertion

To insert an element into a BST, we start at the root node and compare the element’s value with the current node’s value. If it is less than the current node’s value, we move to the left child.

If it is greater, we move to the right child. We repeat this process until we find an empty spot (null node) where we can add the new element as a leaf node.

### Deletion

Deleting an element from a BST can be more complex than searching or inserting. There are several cases to consider: deleting a leaf node, deleting a node with one child, and deleting a node with two children. In each case, we need to carefully rearrange the tree while preserving its ordering property.

## Conclusion

A binary search tree is an efficient data structure for storing and retrieving elements in sorted order. It uses the properties of binary trees and ordering to enable quick search, insertion, and deletion operations. By understanding how BSTs work and how to implement them, you can leverage their benefits in various algorithms and applications.