Binary Tree Implementation in Rust

1. Introduction

A binary tree is a hierarchical data structure in which each node has at most two children: left and right. Binary trees are fundamental for various applications, including expression parsers, Huffman coding trees, and many balanced search tree algorithms. In this post, we'll implement a simple binary tree in Rust.

2. Implementation Steps

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

2. Define the BinaryTree struct that has 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 find 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 BinaryTree<T> {
    root: Link<T>,
}
impl<T: Ord> BinaryTree<T> {
    // Initialize an empty tree
    pub fn new() -> Self {
        BinaryTree { 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)
            }
        }
    }
    // Check if a value exists in the tree
    pub fn find(&self, value: T) -> bool {
        self.find_rec(&self.root, value)
    }
    fn find_rec(&self, node: &Link<T>, value: T) -> bool {
        match node {
            None => false,
            Some(boxed_node) => {
                if value == boxed_node.value {
                    true
                } else if value < boxed_node.value {
                    self.find_rec(&boxed_node.left, value)
                } else {
                    self.find_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 tree = BinaryTree::new();
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);
    println!("In-order traversal: {:?}", tree.in_order());
    println!("Find 25: {}", tree.find(25));
    println!("Find 40: {}", tree.find(40));
}

Output:

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

Explanation:

1. The Node struct represents an individual element in the tree with a value, left child, and right child.

2. The BinaryTree struct contains the root of the tree.

3. The new function provides a way to initialize an empty tree.

4. The insert function allows for adding a value to the tree. It uses a recursive helper function, insert_rec, to navigate and insert the value in the appropriate location.

5. The find function checks if a value exists in the tree, traversing either left or right based on comparisons. The recursive helper find_rec aids in this process.

6. The in_order function retrieves values from the tree in in-order sequence (left, root, right). This uses a recursive helper, in_order_rec, which populates a Vec with the values in order.