binary_search_tree_visualizer/tree/
mod.rs

1use std::fmt::Debug;
2
3/// A node in the binary search tree
4#[derive(Debug)]
5pub struct Node<T> {
6    pub value: T,
7    pub left: Option<Box<Node<T>>>,
8    pub right: Option<Box<Node<T>>>,
9}
10
11impl<T> Node<T> {
12    pub fn new(value: T) -> Self {
13        Self {
14            value,
15            left: None,
16            right: None,
17        }
18    }
19}
20
21/// A binary search tree implementation
22#[derive(Debug)]
23pub struct BinarySearchTree<T> {
24    pub root: Option<Box<Node<T>>>,
25}
26
27impl<T: Ord + Debug> BinarySearchTree<T> {
28    /// Creates a new empty binary search tree
29    pub fn new() -> Self {
30        Self { root: None }
31    }
32
33    /// Inserts a value into the tree
34    pub fn insert(&mut self, value: T) {
35        Self::insert_recursive(&mut self.root, value);
36    }
37
38    fn insert_recursive(node: &mut Option<Box<Node<T>>>, value: T) {
39        match node {
40            None => *node = Some(Box::new(Node::new(value))),
41            Some(ref mut n) => {
42                if value < n.value {
43                    Self::insert_recursive(&mut n.left, value);
44                } else {
45                    Self::insert_recursive(&mut n.right, value);
46                }
47            }
48        }
49    }
50
51    /// Returns the height of the tree
52    pub fn height(&self) -> usize {
53        self.height_recursive(&self.root)
54    }
55
56    fn height_recursive(&self, node: &Option<Box<Node<T>>>) -> usize {
57        match node {
58            None => 0,
59            Some(node) => {
60                1 + std::cmp::max(
61                    self.height_recursive(&node.left),
62                    self.height_recursive(&node.right),
63                )
64            }
65        }
66    }
67
68    /// Returns an iterator over the tree nodes in-order
69    pub fn inorder(&self) -> InOrderIterator<T> {
70        InOrderIterator::new(&self.root)
71    }
72}
73
74/// Iterator for in-order traversal of the tree
75pub struct InOrderIterator<'a, T> {
76    stack: Vec<&'a Node<T>>,
77    current: Option<&'a Node<T>>,
78}
79
80impl<'a, T> InOrderIterator<'a, T> {
81    fn new(root: &'a Option<Box<Node<T>>>) -> Self {
82        let mut iter = Self {
83            stack: Vec::new(),
84            current: None,
85        };
86        if let Some(node) = root {
87            iter.current = Some(node);
88        }
89        iter
90    }
91}
92
93impl<'a, T> Iterator for InOrderIterator<'a, T> {
94    type Item = &'a T;
95
96    fn next(&mut self) -> Option<Self::Item> {
97        while let Some(node) = self.current {
98            self.stack.push(node);
99            self.current = node.left.as_deref();
100        }
101
102        if let Some(node) = self.stack.pop() {
103            self.current = node.right.as_deref();
104            Some(&node.value)
105        } else {
106            None
107        }
108    }
109}
binary_search_tree_visualizer/tree/mod.rs

binary_search_tree_visualizer/tree/
mod.rs
