# Binary Search Trees

Source: https://wisconsin.twango.dev/sp25-cs400/topics/binary-search-trees

# Binary Search Trees

Binary Search Trees are discussed in [[fa24-cs300/u5-hierarchical-data/binary-search-trees|COMP-SCI-300]].

For sake of review, a binary search tree (BST) is a binary tree in which each node has a key value and satisfies the following properties:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. The left and right subtrees are also binary search trees.

## Rotations

### Left Rotation

Original Tree:
```mermaid
%% Left Rotation: BEFORE
flowchart TB
X((x)) --> A((A))
X --> Y((y))
Y --> B((B))
Y --> C((C))
```

After Left Rotation:
```mermaid
%% Left Rotation: AFTER
flowchart TB
    Y((y)) --> X((x))
    X --> A((A))
    X --> B((B))
    Y --> C((C))
```


### Right Rotation

Original Tree
```mermaid
%% Right Rotation: BEFORE
flowchart TB
    X((x)) --> Y((y))
    Y --> A((A))
    Y --> B((B))
    X --> C((C))
```
After Right Rotation:
```mermaid
%% Right Rotation: AFTER
flowchart TB
    Y((y)) --> A((A))
    Y --> X((x))
    X --> B((B))
    X --> C((C))

```

## Time Complexity

A rotation changes a constant number of references: $O(1)$ once the parent and child are known. Locating those nodes separately may cost $O(h)$ for tree height $h$.

## Connections

- [[sp25-cs400/topics/index|Topic index]]

Obvious technical and formatting errors repaired.