Travel BST

Binary Search Tree (BST)

data structure:

left subtree nodes are less than root node
right subtree nodes are greater than root node
left and right subtree are also binary search tree
empty node is also binary search tree

insert new node:

find the position
insert left tree if val < current node
insert right tree if val >= current node
keep the binary search tree property
repeat 1-4

Implement BST with Box<T>

 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
// Maybe I should use a reference count instead of a box pointer
// for the bfs method.
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct BinarySearchBoxNode {
    val: i32,
    left: Option<Box<Self>>,
    right: Option<Box<Self>>,
}

impl BinarySearchBoxNode {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, val: i32) {
        if val < self.val {
            if let Some(left) = &mut self.left {
                left.insert(val);
            } else {
                self.left = Some(Box::new(Self::new(val)));
            }
            return;
        }
        if let Some(right) = &mut self.right {
            right.insert(val);
        } else {
            self.right = Some(Box::new(Self::new(val)));
        }
    }

}

BFS vs DFS

Key Differences:

Data Structure: BFS uses a queue, DFS uses a stack (or recursion).
Traversal Order: BFS visits nodes level by level, DFS goes deep first.
Memory Usage: BFS can use more memory for wide trees, DFS can use less.
Path Finding: BFS finds the shortest path in unweighted graphs, DFS does not guarantee this.
Application: BFS for finding closest nodes, DFS for path existence or tree cloning.

breadth first search

Traverses the tree level by level.
Uses a queue data structure.
Finds the shortest path in an unweighted graph.
Requires more memory for large trees because it stores all nodes at a level.
Good for finding the closest nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
use std::collections::VecDeque;

impl BinarySearchBoxNode {
    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        // maybe I should use a reference count instead of a box pointer
        queue.push_back(Box::new(self.clone())); 
        while let Some(v) = queue.pop_front() {
            result.push(v.val);
            if let Some(left) = v.left {
                queue.push_back(left)
            }
            if let Some(right) = v.right {
                queue.push_back(right);
            }
        }
        result
    }
}

depth first search

Traverses the tree by going as deep as possible before backtracking.
Uses a stack (implicitly through recursion).
Can be implemented recursively or iteratively.
Requires less memory than BFS for deep trees.
Not guaranteed to find the shortest path.
Good for checking if a path exists.

Preorder Traversal

Visit (Process) the current node FIRST. Then, recursively traverse the left subtree. Finally, recursively traverse the right subtree.

Order: Node -> Left -> Right

Use Cases:

Creating a copy of a tree.
Getting prefix expressions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl BinarySearchBoxNode {
    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }
    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_preorder_recursive(result);
        }
    }
}

Inorder Traversal

Recursively traverse the left subtree FIRST. Then, Visit (Process) the current node. Finally, recursively traverse the right subtree.

Order: Left -> Node -> Right

Use Cases:

In Binary Search Trees (BSTs), inorder traversal yields nodes in sorted order.
Getting infix expressions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl BinarySearchBoxNode {
    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }
    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.dfs_inorder_recursive(result);
        }
    }
}

Postorder Traversal

Recursively traverse the left subtree FIRST. Then, recursively traverse the right subtree. Finally, Visit (Process) the current node.

Order: Left -> Right -> Node

Use Cases:

Deleting a tree.
Getting postfix expressions.
Evaluating expression trees.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl BinarySearchBoxNode {
    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }
    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }

Implement BST with Rc<Refcell<T> >

  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
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct BinarySearchNode {
    val: i32,
    left: Option<Rc<RefCell<Self>>>,
    right: Option<Rc<RefCell<Self>>>,
}

impl BinarySearchTree for BinarySearchNode {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, val: i32) {
        if val < self.val {
            if let Some(left) = &mut self.left {
                left.borrow_mut().insert(val);
            } else {
                self.left = Some(Rc::new(RefCell::new(Self::new(val))));
            }
            return;
        }
        if let Some(right) = &mut self.right {
            right.borrow_mut().insert(val);
        } else {
            self.right = Some(Rc::new(RefCell::new(Self::new(val))));
        }
    }

    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(Rc::new(RefCell::new(Self {
            val: self.val,
            left: self.left.clone(),
            right: self.right.clone(),
        })));

        while let Some(node) = queue.pop_front() {
            result.push(node.borrow().val);

            if let Some(left) = &node.borrow().left {
                queue.push_back(left.clone());
            }
            if let Some(right) = &node.borrow().right {
                queue.push_back(right.clone());
            }
        }

        result
    }

    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }

    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.borrow().dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_preorder_recursive(result);
        }
    }

    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }

    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.borrow().dfs_inorder_recursive(result);
        }
    }

    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }

    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }
}

Test snippet

  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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

pub trait BinarySearchTree {
    fn new(val: i32) -> Self;
    fn insert(&mut self, val: i32);
    fn bfs(&self) -> Vec<i32>;
    fn dfs_preorder(&self) -> Vec<i32>;
    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>);
    fn dfs_inorder(&self) -> Vec<i32>;
    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>);
    fn dfs_postorder(&self) -> Vec<i32>;
    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>);
}

// Maybe I should use a reference count instead of a box pointer
// for the bfs method.
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct BinarySearchBoxNode {
    val: i32,
    left: Option<Box<Self>>,
    right: Option<Box<Self>>,
}

impl BinarySearchTree for BinarySearchBoxNode {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, val: i32) {
        if val < self.val {
            if let Some(left) = &mut self.left {
                left.insert(val);
            } else {
                self.left = Some(Box::new(Self::new(val)));
            }
            return;
        }
        if let Some(right) = &mut self.right {
            right.insert(val);
        } else {
            self.right = Some(Box::new(Self::new(val)));
        }
    }

    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(Box::new(self.clone())); // maybe I should use a reference count instead of a box pointer
        while let Some(v) = queue.pop_front() {
            result.push(v.val);
            if let Some(left) = v.left {
                queue.push_back(left)
            }
            if let Some(right) = v.right {
                queue.push_back(right);
            }
        }
        result
    }
    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }
    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_preorder_recursive(result);
        }
    }
    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }
    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.dfs_inorder_recursive(result);
        }
    }
    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }
    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }
}

#[derive(Debug, PartialEq, Eq)]
pub struct BinarySearchNode {
    val: i32,
    left: Option<Rc<RefCell<Self>>>,
    right: Option<Rc<RefCell<Self>>>,
}

impl BinarySearchTree for BinarySearchNode {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, val: i32) {
        if val < self.val {
            if let Some(left) = &mut self.left {
                left.borrow_mut().insert(val);
            } else {
                self.left = Some(Rc::new(RefCell::new(Self::new(val))));
            }
            return;
        }
        if let Some(right) = &mut self.right {
            right.borrow_mut().insert(val);
        } else {
            self.right = Some(Rc::new(RefCell::new(Self::new(val))));
        }
    }

    fn bfs(&self) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(Rc::new(RefCell::new(Self {
            val: self.val,
            left: self.left.clone(),
            right: self.right.clone(),
        })));

        while let Some(node) = queue.pop_front() {
            result.push(node.borrow().val);

            if let Some(left) = &node.borrow().left {
                queue.push_back(left.clone());
            }
            if let Some(right) = &node.borrow().right {
                queue.push_back(right.clone());
            }
        }

        result
    }

    fn dfs_preorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_preorder_recursive(&mut result);
        result
    }

    fn dfs_preorder_recursive(&self, result: &mut Vec<i32>) {
        result.push(self.val);
        if let Some(left) = &self.left {
            left.borrow().dfs_preorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_preorder_recursive(result);
        }
    }

    fn dfs_inorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_inorder_recursive(&mut result);
        result
    }

    fn dfs_inorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_inorder_recursive(result);
        }
        result.push(self.val);
        if let Some(right) = &self.right {
            right.borrow().dfs_inorder_recursive(result);
        }
    }

    fn dfs_postorder(&self) -> Vec<i32> {
        let mut result = Vec::new();
        self.dfs_postorder_recursive(&mut result);
        result
    }

    fn dfs_postorder_recursive(&self, result: &mut Vec<i32>) {
        if let Some(left) = &self.left {
            left.borrow().dfs_postorder_recursive(result);
        }
        if let Some(right) = &self.right {
            right.borrow().dfs_postorder_recursive(result);
        }
        result.push(self.val);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    fn create_binary_tree<T: BinarySearchTree>() -> T {
        let mut root = T::new(5);
        root.insert(3);
        root.insert(7);
        root.insert(2);
        root.insert(4);
        root.insert(6);
        root.insert(8);
        root
    }

    #[test]
    fn test_insert_and_bfs() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.bfs(), vec![5, 3, 7, 2, 4, 6, 8]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.bfs(), vec![5, 3, 7, 2, 4, 6, 8]);
    }

    #[test]
    fn test_dfs_preorder() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.dfs_preorder(), vec![5, 3, 2, 4, 7, 6, 8]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.dfs_preorder(), vec![5, 3, 2, 4, 7, 6, 8]);
    }

    #[test]
    fn test_dfs_inorder() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.dfs_inorder(), vec![2, 3, 4, 5, 6, 7, 8]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.dfs_inorder(), vec![2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn test_dfs_postorder() {
        let root: BinarySearchNode = create_binary_tree();
        assert_eq!(root.dfs_postorder(), vec![2, 4, 3, 6, 8, 7, 5]);
        let root: BinarySearchBoxNode = create_binary_tree();
        assert_eq!(root.dfs_postorder(), vec![2, 4, 3, 6, 8, 7, 5]);
    }

    #[test]
    fn test_single_node() {
        let root = BinarySearchNode::new(10);
        assert_eq!(root.bfs(), vec![10]);
        assert_eq!(root.dfs_preorder(), vec![10]);
        assert_eq!(root.dfs_inorder(), vec![10]);
        assert_eq!(root.dfs_postorder(), vec![10]);
        let root = BinarySearchBoxNode::new(10);
        assert_eq!(root.bfs(), vec![10]);
        assert_eq!(root.dfs_preorder(), vec![10]);
        assert_eq!(root.dfs_inorder(), vec![10]);
        assert_eq!(root.dfs_postorder(), vec![10]);
    }
}

Analysis of BFS and DFS on a BST

Feature	BFS (Breadth-First Search)	DFS (Depth-First Search)
Time Complexity	O(n)	O(n)
Space Complexity	O(w)	O(h)
Explanation	- BFS visits all nodes once, hence O(n). - Space complexity is determined by the maximum width (w) of the tree, as it stores nodes at the current level in a queue.	- DFS visits all nodes once, hence O(n). - Space complexity is determined by the maximum height (h) of the tree, as it stores nodes in the call stack.
Notes	- In a balanced BST, w is roughly n/2, and h is log(n). - In a skewed BST, w can be n, and h can be n.

Binary Search Tree (BST)#

Implement BST with Box<T>#

BFS vs DFS#

breadth first search#

depth first search#

Preorder Traversal#

Inorder Traversal#

Postorder Traversal#

Implement BST with Rc<Refcell<T> >#

Test snippet#

Analysis of BFS and DFS on a BST#

Binary Search Tree (BST)

Implement BST with Box<T>

BFS vs DFS

breadth first search

depth first search

Preorder Traversal

Inorder Traversal

Postorder Traversal

Implement BST with Rc<Refcell<T> >

Test snippet

Analysis of BFS and DFS on a BST