binary-search-tree-visualizer 0.1.0

A crate that provides visualization tools for binary search trees, including ASCII art and SVG generation. Great for educational purposes and debugging.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use std::fmt::Debug;

/// A node in the binary search tree
#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub left: Option<Box<Node<T>>>,
    pub right: Option<Box<Node<T>>>,
}

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

/// A binary search tree implementation
#[derive(Debug)]
pub struct BinarySearchTree<T> {
    pub root: Option<Box<Node<T>>>,
}

impl<T: Ord + Debug> BinarySearchTree<T> {
    /// Creates a new empty binary search tree
    pub fn new() -> Self {
        Self { root: None }
    }

    /// Inserts a value into the tree
    pub fn insert(&mut self, value: T) {
        Self::insert_recursive(&mut self.root, value);
    }

    fn insert_recursive(node: &mut Option<Box<Node<T>>>, value: T) {
        match node {
            None => *node = Some(Box::new(Node::new(value))),
            Some(ref mut n) => {
                if value < n.value {
                    Self::insert_recursive(&mut n.left, value);
                } else {
                    Self::insert_recursive(&mut n.right, value);
                }
            }
        }
    }

    /// Returns the height of the tree
    pub fn height(&self) -> usize {
        self.height_recursive(&self.root)
    }

    fn height_recursive(&self, node: &Option<Box<Node<T>>>) -> usize {
        match node {
            None => 0,
            Some(node) => {
                1 + std::cmp::max(
                    self.height_recursive(&node.left),
                    self.height_recursive(&node.right),
                )
            }
        }
    }

    /// Returns an iterator over the tree nodes in-order
    pub fn inorder(&self) -> InOrderIterator<T> {
        InOrderIterator::new(&self.root)
    }
}

/// Iterator for in-order traversal of the tree
pub struct InOrderIterator<'a, T> {
    stack: Vec<&'a Node<T>>,
    current: Option<&'a Node<T>>,
}

impl<'a, T> InOrderIterator<'a, T> {
    fn new(root: &'a Option<Box<Node<T>>>) -> Self {
        let mut iter = Self {
            stack: Vec::new(),
            current: None,
        };
        if let Some(node) = root {
            iter.current = Some(node);
        }
        iter
    }
}

impl<'a, T> Iterator for InOrderIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(node) = self.current {
            self.stack.push(node);
            self.current = node.left.as_deref();
        }

        if let Some(node) = self.stack.pop() {
            self.current = node.right.as_deref();
            Some(&node.value)
        } else {
            None
        }
    }
}