Binary Search Tree Implementation in Rust

1. Introduction

A Binary Search Tree (BST) is a binary tree where each node has a value, and the left subtree of a node contains only nodes with values less than the node's value, and the right subtree only nodes with values greater than the node's value. This property ensures that operations like insert, delete, and search can be carried out efficiently. In this post, we will implement a basic BST in Rust.

2. Implementation Steps

1. Define a Node struct with value, left, and right attributes.

2. Define the BinarySearchTree struct that will contain a root node.

3. Implement a new function to initialize an empty tree.

4. Implement an insert function to add a node to the tree.

5. Implement a search function to check if a value exists in the tree.

6. Implement an in_order function for in-order traversal.

3. Implementation in Rust Programming

type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
    value: T,
    left: Link<T>,
    right: Link<T>,
}
pub struct BinarySearchTree<T> {
    root: Link<T>,
}
impl<T: Ord> BinarySearchTree<T> {
    // Initialize an empty tree
    pub fn new() -> Self {
        BinarySearchTree { root: None }
    }
    // Insert a value into the tree
    pub fn insert(&mut self, value: T) {
        self.root = self.insert_rec(self.root.take(), value);
    }
    fn insert_rec(&self, node: Link<T>, value: T) -> Link<T> {
        match node {
            None => Some(Box::new(Node {
                value,
                left: None,
                right: None,
            })),
            Some(mut boxed_node) => {
                if value < boxed_node.value {
                    boxed_node.left = self.insert_rec(boxed_node.left, value);
                } else if value > boxed_node.value {
                    boxed_node.right = self.insert_rec(boxed_node.right, value);
                }
                Some(boxed_node)
            }
        }
    }
    // Search for a value in the tree
    pub fn search(&self, value: T) -> bool {
        self.search_rec(&self.root, value)
    }
    fn search_rec(&self, node: &Link<T>, value: T) -> bool {
        match node {
            None => false,
            Some(ref boxed_node) => {
                if value == boxed_node.value {
                    true
                } else if value < boxed_node.value {
                    self.search_rec(&boxed_node.left, value)
                } else {
                    self.search_rec(&boxed_node.right, value)
                }
            }
        }
    }
    // In-order traversal of the tree
    pub fn in_order(&self) -> Vec<&T> {
        let mut result = Vec::new();
        self.in_order_rec(&self.root, &mut result);
        result
    }
    fn in_order_rec(&self, node: &Link<T>, result: &mut Vec<&T>) {
        if let Some(ref boxed_node) = *node {
            self.in_order_rec(&boxed_node.left, result);
            result.push(&boxed_node.value);
            self.in_order_rec(&boxed_node.right, result);
        }
    }
}
fn main() {
    let mut bst = BinarySearchTree::new();
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(20);
    bst.insert(40);
    bst.insert(60);
    bst.insert(80);
    println!("In-order traversal: {:?}", bst.in_order());
    println!("Search 25: {}", bst.search(25));
    println!("Search 40: {}", bst.search(40));
}

Output:

In-order traversal: [20, 30, 40, 50, 60, 70, 80]
Search 25: false
Search 40: true

Explanation:

1. The Node struct represents each element in the BST. Each Node has a value, a left child, and a right child.

2. The BinarySearchTree struct represents the tree itself, containing a root which is the starting point of our tree.

3. The new function allows for the initialization of an empty tree.

4. The insert function is utilized to add values to the BST. It employs a recursive helper function, insert_rec, to navigate through the tree and insert the value in the appropriate location based on the BST properties.

5. The search function checks for the presence of a value in the tree. This function uses the recursive helper, search_rec, to traverse the tree while comparing values.

6. The in_order function provides an in-order traversal of the BST, which means it will return values in ascending order. The in_order_rec helper function recursively fetches the values.