Binary Search Tree (BST)

A binary search tree (BST) is a special type of binary tree that maintains an ordering property. This property allows efficient searching, insertion, and deletion operations by systematically eliminating half of the remaining nodes during traversal.

BSTs combine the hierarchical structure of trees with the efficiency of binary search.

BST Property

For every node in a binary search tree:

• All values in the left subtree are less than the node’s value
• All values in the right subtree are greater than the node’s value
• Both subtrees are themselves binary search trees

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

This ordering makes it possible to decide which direction to move at each step during search.

Basic Operations

A binary search tree supports three core operations:

1. Search
2. Insertion
3. Deletion

This section focuses on search and insertion, which establish the BST structure.

Searching in a BST

To search for a value:

1. Start at the root
2. If the value is equal → found
3. If the value is smaller → go left
4. If the value is larger → go right

This process continues until the value is found or a leaf is reached.

Inserting into a BST

Insertion follows the same logic as search:

• Traverse the tree based on comparisons
• Insert the new value at the correct leaf position
• The BST property is preserved automatically

Rust Implementation

Below is a clean and idiomatic BST implementation supporting insert and search.

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub left: Option<Box<Node<T>>>,
    pub right: Option<Box<Node<T>>>,
}

impl<T: Ord> Node<T> {
    pub fn new(value: T) -> Self {
        Node {
            value,
            left: None,
            right: None,
        }
    }

    pub fn insert(&mut self, value: T) {
        if value < self.value {
            match self.left {
                Some(ref mut left) => left.insert(value),
                None => self.left = Some(Box::new(Node::new(value))),
            }
        } else if value > self.value {
            match self.right {
                Some(ref mut right) => right.insert(value),
                None => self.right = Some(Box::new(Node::new(value))),
            }
        }
        // Duplicate values are ignored
    }

    pub fn contains(&self, value: &T) -> bool {
        if value == &self.value {
            true
        } else if value < &self.value {
            match self.left {
                Some(ref left) => left.contains(value),
                None => false,
            }
        } else {
            match self.right {
                Some(ref right) => right.contains(value),
                None => false,
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_inserts_and_searches() {
        let mut root = Node::new(8);
        root.insert(3);
        root.insert(10);
        root.insert(1);
        root.insert(6);
        root.insert(14);

        assert!(root.contains(&6));
        assert!(!root.contains(&7));
    }
}

Example Usage

fn main() {
    let mut bst = Node::new(8);

    bst.insert(3);
    bst.insert(10);
    bst.insert(1);
    bst.insert(6);
    bst.insert(14);

    println!("Contains 6? {}", bst.contains(&6));
    println!("Contains 7? {}", bst.contains(&7));
}

Time and Space Complexity

BST performance depends on how balanced the tree is.

Time Complexity

Space Complexity

Limitations of BSTs

A plain BST does not guarantee balance. Inserting sorted data can degrade it into a linked list:

1 → 2 → 3 → 4 → 5

This is why self-balancing trees such as AVL and Red-Black trees exist.

Playground Links

Rust - Binary Search Tree