bst_rs/lib.rs
1//! This crate contains Recursive & Iterative Binary Search Tree Implementations. All common operations are included along with common traversal iterators.
2//!
3//! All elements within the Binary Search Trees _must_ implement the [Ord] trait.
4//!
5//! It is also important to note that [RecursiveBST] is more likely to `blow the stack.`
6//! For more information on why that is the case, please have a look at
7//! [The Story of Tail Call Optimizations in Rust.](https://seanchen1991.github.io/posts/tco-story/)
8//!
9//! ## Author Notes
10//!
11//! I have made this library with the personal goals of learning and solidifying concepts such
12//! as **ownership**, **borrowing**, **generics** and **lifetimes**. I cannot promise that the implementations are
13//! particularly efficient, or if they are, it was not at the forefront of my mind.
14//!
15//! That being said, there are some areas I would love to improve upon/include:
16//! - Write idiomatic code.
17//! - Effectively use **macro_rules!** to reduce large portions of repetitive code.
18//! - Implement a **pretty_print()** function to display the binary search trees nicely.
19//! - Implement [Drop] trait for iterative node cleanup.
20//! - Pre-allocate space on the heap for nodes to reduce inefficiency of inserts.
21//!
22//! I'm more than happy to accept (and encourage) contributions if anyone is kind enough to do so.
23//!
24//! # Quick Start
25//!
26//! ```rust
27//! use bst_rs::{BinarySearchTree, IterativeBST, RecursiveBST};
28//!
29//! // Create new empty binary search trees
30//! let mut iterative_bst = IterativeBST::new();
31//! assert!(iterative_bst.is_empty());
32//!
33//! let mut recursive_bst = RecursiveBST::new();
34//! assert!(recursive_bst.is_empty());
35//!
36//! // Insert elements (no duplicates are allowed)
37//! iterative_bst.insert(10);
38//! iterative_bst.insert(10); // Element is not inserted
39//! iterative_bst.insert(5);
40//! iterative_bst.insert(2);
41//! iterative_bst.insert(15);
42//! iterative_bst.insert(25);
43//! assert_eq!(iterative_bst.size(), 5);
44//!
45//! recursive_bst.insert(10);
46//! recursive_bst.insert(10); // Element is not inserted
47//! recursive_bst.insert(5);
48//! recursive_bst.insert(2);
49//! recursive_bst.insert(15);
50//! recursive_bst.insert(25);
51//! assert_eq!(recursive_bst.size(), 5);
52//!
53//! // Check if element exists
54//! assert!(iterative_bst.contains(&5)); // true
55//! assert!(!iterative_bst.contains(&0)); // false
56//!
57//! assert!(recursive_bst.contains(&5)); // true
58//! assert!(!recursive_bst.contains(&0)); // false
59//!
60//! // Remove elements
61//! iterative_bst.remove(&10);
62//! iterative_bst.remove(&50); // No change to tree as element does not exist
63//! assert_eq!(iterative_bst.size(), 4);
64//!
65//! recursive_bst.remove(&10);
66//! recursive_bst.remove(&50); // No change to tree as element does not exist
67//! assert_eq!(recursive_bst.size(), 4);
68//!
69//! // View pre-order, in-order, post-order and level-order traversals
70//! assert_eq!(iterative_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
71//! assert_eq!(iterative_bst.in_order_vec(), vec![&2, &5, &15, &25]);
72//! assert_eq!(iterative_bst.post_order_vec(), vec![&2, &5, &25, &15]);
73//! assert_eq!(iterative_bst.level_order_vec(), vec![&15, &5, &25, &2]);
74//!
75//! assert_eq!(recursive_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
76//! assert_eq!(recursive_bst.in_order_vec(), vec![&2, &5, &15, &25]);
77//! assert_eq!(recursive_bst.post_order_vec(), vec![&2, &5, &25, &15]);
78//! assert_eq!(recursive_bst.level_order_vec(), vec![&15, &5, &25, &2]);
79//!
80//! // Compare equality/in-equality of trees
81//! assert_eq!(iterative_bst.asc_order_vec(), recursive_bst.asc_order_vec());
82//! assert_ne!(iterative_bst, IterativeBST::new());
83//! assert_ne!(recursive_bst, RecursiveBST::new());
84//! ```
85
86use std::fmt::{Debug, Display, Formatter};
87use std::vec::IntoIter;
88use crate::node::{HeapNode, Node};
89
90mod node;
91
92/// A trait containing all the common operations of Binary Search Trees.
93///
94/// # Examples
95/// Examples are extended from crate level "Quick Start"
96///
97/// ```rust
98/// use bst_rs::{BinarySearchTree, IterativeBST, RecursiveBST};
99///
100/// // Create new empty binary search trees
101/// let mut iterative_bst = IterativeBST::new();
102/// assert!(iterative_bst.is_empty());///
103///
104/// let mut recursive_bst = RecursiveBST::new();
105/// assert!(recursive_bst.is_empty());
106///
107/// // Insert elements (no duplicates are allowed)
108/// iterative_bst.insert(10);
109/// iterative_bst.insert(10); // Element is not inserted
110/// iterative_bst.insert(5);
111/// iterative_bst.insert(2);
112/// iterative_bst.insert(15);
113/// iterative_bst.insert(25);
114/// assert_eq!(iterative_bst.size(), 5);
115///
116/// recursive_bst.insert(10);
117/// recursive_bst.insert(10); // Element is not inserted
118/// recursive_bst.insert(5);
119/// recursive_bst.insert(2);
120/// recursive_bst.insert(15);
121/// recursive_bst.insert(25);
122/// assert_eq!(recursive_bst.size(), 5);
123///
124/// // Check if element exists
125/// assert!(iterative_bst.contains(&5)); // true
126/// assert!(!iterative_bst.contains(&0)); // false
127///
128/// assert!(recursive_bst.contains(&5)); // true
129/// assert!(!recursive_bst.contains(&0)); // false
130///
131/// // Remove elements
132/// iterative_bst.remove(&10);
133/// iterative_bst.remove(&50); // No change to tree as element does not exist
134/// assert_eq!(iterative_bst.size(), 4);
135///
136/// recursive_bst.remove(&10);
137/// recursive_bst.remove(&50); // No change to tree as element does not exist
138/// assert_eq!(recursive_bst.size(), 4);
139///
140/// // Get height of tree
141/// assert_eq!(iterative_bst.height(), Some(2));
142/// assert_eq!(recursive_bst.height(), Some(2));
143///
144/// // Get minimum element of tree
145/// assert_eq!(iterative_bst.min(), Some(&2));
146/// assert_eq!(recursive_bst.min(), Some(&2));
147///
148/// // Get maximum element of tree
149/// assert_eq!(iterative_bst.max(), Some(&25));
150/// assert_eq!(recursive_bst.max(), Some(&25));
151///
152/// // Retrieve reference to element in tree
153/// assert_eq!(iterative_bst.retrieve(&5), Some(&5));
154/// assert_eq!(iterative_bst.retrieve(&100), None); // Element does not exist so None is returned
155/// assert_eq!(recursive_bst.retrieve(&5), Some(&5));
156/// assert_eq!(recursive_bst.retrieve(&100), None); // Element does not exist so None is returned
157///
158/// // View pre-order, in-order, post-order and level-order traversals
159/// assert_eq!(iterative_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
160/// assert_eq!(iterative_bst.in_order_vec(), vec![&2, &5, &15, &25]);
161/// assert_eq!(iterative_bst.post_order_vec(), vec![&2, &5, &25, &15]);
162/// assert_eq!(iterative_bst.level_order_vec(), vec![&15, &5, &25, &2]);
163///
164/// assert_eq!(recursive_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
165/// assert_eq!(recursive_bst.in_order_vec(), vec![&2, &5, &15, &25]);
166/// assert_eq!(recursive_bst.post_order_vec(), vec![&2, &5, &25, &15]);
167/// assert_eq!(recursive_bst.level_order_vec(), vec![&15, &5, &25, &2]);
168///
169/// // Compare equality/in-equality of trees
170/// assert_eq!(iterative_bst.asc_order_vec(), recursive_bst.asc_order_vec());
171/// assert_ne!(iterative_bst, IterativeBST::new());
172/// assert_ne!(recursive_bst, RecursiveBST::new());
173/// ```
174pub trait BinarySearchTree<T: Ord> {
175 /// Returns the total **number of nodes** within the tree.
176 fn size(&self) -> usize;
177
178 /// Returns `true` if the binary search tree contains no nodes.
179 fn is_empty(&self) -> bool;
180
181 /// Returns `true` if the binary search tree contains one or more nodes.
182 fn is_not_empty(&self) -> bool;
183
184 /// Inserts given value as a node.
185 ///
186 /// **Duplicate values are _not allowed_**.
187 fn insert(&mut self, value: T);
188
189 /// Returns `true` if the binary search tree contains an element with the given value.
190 fn contains(&self, value: &T) -> bool;
191
192 /// Removes the given value.
193 ///
194 /// Tree will not be modified if trying to remove element that does not exist.
195 fn remove(&mut self, value: &T);
196
197 /// Returns a reference to the element or `None` if element does not exist.
198 fn retrieve(&self, value: &T) -> Option<&T>;
199
200 /// Returns a mutable reference to the element (see [`retrieve`](Self::retrieve()))
201 /// or `None` if element does not exist.
202 fn retrieve_as_mut(&mut self, value: &T) -> Option<&mut T>;
203
204 /// Returns the **height** or `None` if tree is empty.
205 ///
206 /// The height is the number of edges between the root and it's furthest leaf node.
207 ///
208 /// # Example
209 ///
210 /// Given a tree that looks like:
211 ///
212 /// ```rust
213 /// // 4
214 /// // / \
215 /// // 2 6
216 /// // / \ / \
217 /// // 1 3 5 7
218 /// ```
219 ///
220 /// The height is: **2**
221 fn height(&self) -> Option<isize>;
222
223 /// Returns a reference to the minimum element of the tree or `None` if tree is empty.
224 fn min(&self) -> Option<&T>;
225
226 /// Returns a reference to the maximum element of the tree or `None` if tree is empty.
227 fn max(&self) -> Option<&T>;
228
229 /// Removes and returns the minimum element from the tree or `None` if tree is empty.
230 fn remove_min(&mut self) -> Option<T>;
231
232 /// Removes and returns the maximum element from the tree or `None` if tree is empty.
233 fn remove_max(&mut self) -> Option<T>;
234
235 /// Returns references to the elements of the tree in **ascending order.**
236 ///
237 /// # Important
238 ///
239 /// This is function is analogous to [in_order_vec](Self::in_order_vec()) as the underlying
240 /// behaviour is **_exactly the same_.**
241 fn asc_order_vec(&self) -> Vec<&T>;
242
243 /// Returns references to the elements of the tree in the order of a **pre-order traversal.**
244 ///
245 /// # Example
246 ///
247 /// Given a tree that looks like:
248 /// ```rust
249 /// // 4
250 /// // / \
251 /// // 2 6
252 /// // / \ / \
253 /// // 1 3 5 7
254 /// ```
255 /// The pre_order_vec is: **[&4, &2, &1, &3, &6, &5, &7].**
256 fn pre_order_vec(&self) -> Vec<&T>;
257
258 /// Returns references to the elements of the tree in the order of an **in-order traversal.**
259 ///
260 /// # Important
261 ///
262 /// This is function is analogous to [asc_order_vec](Self::asc_order_vec()) as the underlying
263 /// behaviour is **_exactly the same_.**
264 ///
265 /// # Example
266 ///
267 /// Given a tree that looks like:
268 /// ```rust
269 /// // 4
270 /// // / \
271 /// // 2 6
272 /// // / \ / \
273 /// // 1 3 5 7
274 /// ```
275 /// The in_order_vec is: **[&1, &2, &3, &4, &5, &6, &7].**
276 fn in_order_vec(&self) -> Vec<&T>;
277
278 /// Returns references to the elements of the tree in the order of a **post-order traversal.**
279 ///
280 /// # Example
281 ///
282 /// Given a tree that looks like:
283 /// ```rust
284 /// // 4
285 /// // / \
286 /// // 2 6
287 /// // / \ / \
288 /// // 1 3 5 7
289 /// ```
290 /// The post_order_vec is: **[&1, &3, &2, &5, &7, &6, &4].**
291 fn post_order_vec(&self) -> Vec<&T>;
292
293 /// Returns references to the elements of the tree in the order of a **level-order traversal.**
294 ///
295 /// # Example
296 ///
297 /// Given a tree that looks like:
298 /// ```rust
299 /// // 4
300 /// // / \
301 /// // 2 6
302 /// // / \ / \
303 /// // 1 3 5 7
304 /// ```
305 /// The post_order_vec is: **[&4, &2, &6, &1, &3, &5, &7].**
306 fn level_order_vec(&self) -> Vec<&T>;
307
308 /// Returns an iterator over [asc_order_vec](Self::asc_order_vec()).
309 ///
310 /// # Important
311 ///
312 /// This is function is analogous to [in_order_iter](Self::in_order_iter()) as the underlying
313 /// behaviour is **_exactly the same_.**
314 fn asc_order_iter(&self) -> IntoIter<&T>;
315
316 /// Returns an iterator over [pre_order_vec](Self::pre_order_vec()).
317 fn pre_order_iter(&self) -> IntoIter<&T>;
318
319 /// Returns an iterator over [in_order_vec](Self::in_order_vec()).
320 ///
321 /// # Important
322 ///
323 /// This is function is analogous to [asc_order_iter](Self::asc_order_iter()) as the underlying
324 /// behaviour is **_exactly the same_.**
325 fn in_order_iter(&self) -> IntoIter<&T>;
326
327 /// Returns an iterator over [post_order_vec](Self::post_order_vec()).
328 fn post_order_iter(&self) -> IntoIter<&T>;
329
330 /// Returns an iterator over [level_order_vec](Self::level_order_vec()).
331 fn level_order_iter(&self) -> IntoIter<&T>;
332
333 /// Returns [asc_order_iter](Self::asc_order_iter()) **AND** consumes the tree.
334 ///
335 /// # Important
336 ///
337 /// This is function is analogous to [into_in_order_iter](Self::into_in_order_iter()) as the
338 /// underlying behaviour is **_exactly the same_.**
339 fn into_asc_order_iter(self) -> IntoIter<T>;
340
341 /// Returns [pre_order_iter](Self::pre_order_iter()) **AND** consumes the tree.
342 fn into_pre_order_iter(self) -> IntoIter<T>;
343
344 /// Returns [in_order_iter](Self::in_order_iter()) **AND** consumes the tree.
345 ///
346 /// # Important
347 ///
348 /// This is function is analogous to [into_asc_order_iter](Self::into_asc_order_iter()) as the
349 /// underlying behaviour is **_exactly the same_.**
350 fn into_in_order_iter(self) -> IntoIter<T>;
351
352 /// Returns [post_order_iter](Self::post_order_iter()) **AND** consumes the tree.
353 fn into_post_order_iter(self) -> IntoIter<T>;
354
355 /// Returns [level_order_iter](Self::level_order_iter()) **AND** consumes the tree.
356 fn into_level_order_iter(self) -> IntoIter<T>;
357}
358
359/// Recursive Binary Search Tree implementation.
360///
361/// # Important
362///
363/// It is also important to note that [RecursiveBST] is more likely to **blow the stack** and is
364/// generally less performant compared to [IterativeBST].
365///
366/// For more information on why that is the case, please have a look at
367/// [The Story of Tail Call Optimizations in Rust.](https://seanchen1991.github.io/posts/tco-story/)
368#[derive(Debug)]
369pub struct RecursiveBST<T: Ord> {
370 root: HeapNode<T>,
371 size: usize,
372}
373
374/// Iterative Binary Search Tree implementation.
375///
376/// # Important
377///
378/// This should be preferred over [RecursiveBST] for reasons listed in crate level documentation.
379#[derive(Debug)]
380pub struct IterativeBST<T: Ord> {
381 root: HeapNode<T>,
382 size: usize,
383}
384
385impl<T: Ord> IterativeBST<T> {
386 /// Creates an empty `IterativeBST<T>`
387 ///
388 /// No nodes are allocated on the heap yet
389 ///
390 /// # Examples
391 ///
392 /// ```rust
393 /// use bst_rs::{BinarySearchTree, IterativeBST};
394 ///
395 /// // Empty tree is created
396 /// let mut bst: IterativeBST<i32> = IterativeBST::new();
397 /// assert!(bst.is_empty())
398 /// ```
399 pub fn new() -> IterativeBST<T> {
400 IterativeBST {
401 root: None,
402 size: 0,
403 }
404 }
405}
406
407impl<T: Ord> Default for IterativeBST<T> {
408 /// Creates an empty `IterativeBST<T>`
409 fn default() -> IterativeBST<T> {
410 IterativeBST::new()
411 }
412}
413
414impl<T: Ord> PartialEq for IterativeBST<T> {
415 fn eq(&self, other: &Self) -> bool {
416 self.asc_order_vec() == other.asc_order_vec()
417 }
418}
419
420impl<T: Ord> Extend<T> for IterativeBST<T> {
421 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
422 for value in iter.into_iter() {
423 self.insert(value)
424 }
425 }
426}
427
428impl<T: Ord> FromIterator<T> for IterativeBST<T> {
429 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
430 let mut bst = IterativeBST::new();
431 bst.extend(iter);
432 bst
433 }
434}
435
436impl<T: Ord> From<Vec<T>> for IterativeBST<T> {
437 fn from(vec: Vec<T>) -> Self {
438 let mut bst = IterativeBST::new();
439 for value in vec.into_iter() {
440 bst.insert(value);
441 }
442 bst
443 }
444}
445
446impl<T: Ord + Clone> From<&[T]> for IterativeBST<T> {
447 fn from(slice: &[T]) -> Self {
448 let mut bst = IterativeBST::new();
449 for value in slice {
450 bst.insert((*value).clone());
451 }
452 bst
453 }
454}
455
456impl<T: Ord + Clone> Clone for IterativeBST<T> {
457 fn clone(&self) -> Self {
458 let mut bst = IterativeBST::new();
459
460 for value in self.in_order_iter() {
461 bst.insert((*value).clone());
462 }
463
464 bst
465 }
466}
467
468impl<T: Ord + Debug> Display for IterativeBST<T> {
469 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
470 write!(f, "{:?}", self.asc_order_vec())
471 }
472}
473
474impl<T: Ord> BinarySearchTree<T> for IterativeBST<T> {
475 /// Returns the total **number of nodes** within the tree.
476 ///
477 /// # Example
478 ///
479 /// ```rust
480 /// use bst_rs::{BinarySearchTree, IterativeBST};
481 ///
482 /// let mut bst = IterativeBST::new();
483 /// bst.insert(5);
484 /// bst.insert(10);
485 /// bst.insert(3);
486 ///
487 /// assert_eq!(bst.size(), 3);
488 /// ```
489 fn size(&self) -> usize {
490 self.size
491 }
492
493 /// Returns `true` if the binary search tree contains no nodes.
494 ///
495 /// # Examples
496 ///
497 /// ```rust
498 /// use bst_rs::{BinarySearchTree, IterativeBST};
499 ///
500 /// let mut bst: IterativeBST<i32> = IterativeBST::new();
501 /// assert!(bst.is_empty());
502 /// ```
503 fn is_empty(&self) -> bool {
504 self.size == 0
505 }
506
507 /// Returns `true` if the binary search tree contains one or more nodes.
508 ///
509 /// # Example
510 ///
511 /// ```rust
512 /// use bst_rs::{BinarySearchTree, IterativeBST};
513 ///
514 /// let mut bst = IterativeBST::new();
515 /// assert!(bst.is_empty());
516 ///
517 /// bst.insert(2);
518 ///
519 /// assert!(bst.is_not_empty());
520 /// ```
521 fn is_not_empty(&self) -> bool {
522 self.size != 0
523 }
524
525 /// Inserts given value as a node.
526 ///
527 /// **Duplicate values are _not allowed_**.
528 ///
529 /// # Example
530 ///
531 /// ```rust
532 /// use bst_rs::{BinarySearchTree, IterativeBST};
533 ///
534 /// let mut bst = IterativeBST::new();
535 ///
536 /// bst.insert(10);
537 /// bst.insert(10); // Element is not inserted
538 /// bst.insert(5);
539 /// bst.insert(2);
540 /// bst.insert(15);
541 /// bst.insert(25);
542 ///
543 /// assert_eq!(bst.size(), 5);
544 /// ```
545 fn insert(&mut self, value: T) {
546 if Node::iterative_insert(&mut self.root, value).is_ok() {
547 self.size += 1;
548 }
549 }
550
551 /// Returns `true` if the binary search tree contains an element with the given value.
552 ///
553 /// # Example
554 ///
555 /// ```rust
556 /// use bst_rs::{BinarySearchTree, IterativeBST};
557 ///
558 /// let mut bst = IterativeBST::new();
559 /// bst.insert(5);
560 /// bst.insert(2);
561 /// bst.insert(7);
562 ///
563 /// assert!(bst.contains(&5));
564 /// assert!(!bst.contains(&10));
565 /// ```
566 fn contains(&self, value: &T) -> bool {
567 Node::iterative_contains(&self.root, value)
568 }
569
570 /// Removes the given value.
571 ///
572 /// Tree will not be modified if trying to remove element that does not exist.
573 ///
574 /// # Example
575 ///
576 /// ```rust
577 /// use bst_rs::{BinarySearchTree, IterativeBST};
578 ///
579 /// let mut bst = IterativeBST::new();
580 /// bst.insert(5);
581 /// bst.insert(2);
582 /// bst.insert(7);
583 /// assert_eq!(bst.size(), 3);
584 ///
585 /// bst.remove(&5);
586 /// bst.remove(&10); // Element is not removed
587 /// assert_eq!(bst.size(), 2);
588 /// ```
589 fn remove(&mut self, value: &T) {
590 if Node::iterative_remove(&mut self.root, value).is_ok() {
591 self.size -= 1;
592 }
593 }
594
595 /// Returns a reference to the element or `None` if element does not exist.
596 ///
597 /// # Example
598 ///
599 /// ```rust
600 /// use bst_rs::{BinarySearchTree, IterativeBST};
601 ///
602 /// let mut bst = IterativeBST::new();
603 /// bst.insert(5);
604 /// bst.insert(2);
605 /// bst.insert(7);
606 ///
607 /// assert_eq!(bst.retrieve(&5), Some(&5));
608 /// assert_eq!(bst.retrieve(&10), None);
609 /// ```
610 fn retrieve(&self, value: &T) -> Option<&T> {
611 Node::iterative_retrieve(&self.root, value)
612 }
613
614 /// Returns a mutable reference to the element (see [IterativeBST::retrieve()])
615 /// or `None` if element does not exist.
616 ///
617 /// # Example
618 ///
619 /// ```rust
620 /// use bst_rs::{BinarySearchTree, IterativeBST};
621 ///
622 /// let mut bst = IterativeBST::new();
623 /// bst.insert(10);
624 /// bst.insert(5);
625 ///
626 /// let optional_retrieved_value_as_mut = bst.retrieve_as_mut(&5);
627 /// assert_eq!(optional_retrieved_value_as_mut, Some(&mut 5));
628 ///
629 /// let mut retrieved_value = optional_retrieved_value_as_mut.unwrap();
630 /// *retrieved_value = 2; // Change value inside tree to '2'
631 ///
632 /// assert_eq!(bst.retrieve_as_mut(&5), None); // 5 does not exist anymore
633 /// assert_eq!(bst.retrieve_as_mut(&2), Some(&mut 2));
634 /// ```
635 fn retrieve_as_mut(&mut self, value: &T) -> Option<&mut T> {
636 Node::iterative_retrieve_as_mut(&mut self.root, value)
637 }
638
639 /// Returns the **height** or `None` if tree is empty.
640 ///
641 /// The height is the number of edges between the root and it's furthest leaf node.
642 ///
643 /// # Example
644 ///
645 /// ```rust
646 /// use bst_rs::{BinarySearchTree, IterativeBST};
647 ///
648 /// // Given a tree that looks like:
649 /// // 4
650 /// // / \
651 /// // 2 6
652 /// // / \ / \
653 /// // 1 3 5 7
654 /// let mut bst = IterativeBST::new();
655 /// assert_eq!(bst.height(), None);
656 ///
657 /// bst.insert(4);
658 /// bst.insert(6);
659 /// bst.insert(2);
660 /// bst.insert(7);
661 /// bst.insert(5);
662 /// bst.insert(3);
663 /// bst.insert(1);
664 ///
665 /// // The height is 2.
666 /// assert_eq!(bst.height(), Some(2));
667 /// ```
668 fn height(&self) -> Option<isize> {
669 self.root
670 .as_ref()
671 .map(|_| Node::iterative_height(&self.root))
672 }
673
674 /// Returns a reference to the minimum element of the tree or `None` if tree is empty.
675 ///
676 /// # Example
677 ///
678 /// ```rust
679 /// use bst_rs::{BinarySearchTree, IterativeBST};
680 ///
681 /// let mut bst = IterativeBST::new();
682 /// assert_eq!(bst.min(), None);
683 ///
684 /// bst.insert(5);
685 /// bst.insert(2);
686 /// bst.insert(10);
687 ///
688 /// assert_eq!(bst.min(), Some(&2));
689 /// ```
690 fn min(&self) -> Option<&T> {
691 Node::iterative_min(&self.root)
692 }
693
694 /// Returns a reference to the maximum element of the tree or `None` if tree is empty.
695 ///
696 /// # Example
697 ///
698 /// ```rust
699 /// use bst_rs::{BinarySearchTree, IterativeBST};
700 ///
701 /// let mut bst = IterativeBST::new();
702 /// assert_eq!(bst.max(), None);
703 ///
704 /// bst.insert(5);
705 /// bst.insert(2);
706 /// bst.insert(10);
707 ///
708 /// assert_eq!(bst.max(), Some(&10));
709 /// ```
710 fn max(&self) -> Option<&T> {
711 Node::iterative_max(&self.root)
712 }
713
714 /// Removes and returns the minimum element from the tree or `None` if tree is empty.
715 ///
716 /// # Example
717 ///
718 /// ```rust
719 /// use bst_rs::{BinarySearchTree, IterativeBST};
720 ///
721 /// let mut bst = IterativeBST::new();
722 /// assert_eq!(bst.remove_min(), None);
723 ///
724 /// bst.insert(2);
725 /// bst.insert(5);
726 /// bst.insert(10);
727 ///
728 /// assert_eq!(bst.size(), 3);
729 /// assert_eq!(bst.remove_min(), Some(2));
730 /// assert_eq!(bst.size(), 2);
731 /// ```
732 fn remove_min(&mut self) -> Option<T> {
733 let removed_min = Node::iterative_remove_min(&mut self.root);
734 if removed_min.is_some() {
735 self.size -= 1;
736 }
737 removed_min
738 }
739
740 /// Removes and returns the maximum element from the tree or `None` if tree is empty.
741 ///
742 /// # Example
743 ///
744 /// ```rust
745 /// use bst_rs::{BinarySearchTree, IterativeBST};
746 ///
747 /// let mut bst = IterativeBST::new();
748 /// assert_eq!(bst.remove_max(), None);
749 ///
750 /// bst.insert(2);
751 /// bst.insert(5);
752 /// bst.insert(10);
753 ///
754 /// assert_eq!(bst.size(), 3);
755 /// assert_eq!(bst.remove_max(), Some(10));
756 /// assert_eq!(bst.size(), 2);
757 /// ```
758 fn remove_max(&mut self) -> Option<T> {
759 let removed_max = Node::iterative_remove_max(&mut self.root);
760 if removed_max.is_some() {
761 self.size -= 1;
762 }
763 removed_max
764 }
765
766 /// Returns references to the elements of the tree in **ascending order.**`
767 ///
768 /// # Important
769 ///
770 /// This is function is analogous to [IterativeBST::in_order_vec()] as the underlying
771 /// behaviour is **_exactly the same_.**
772 ///
773 /// # Example
774 ///
775 /// ```rust
776 /// use bst_rs::{BinarySearchTree, IterativeBST};
777 ///
778 /// let mut bst = IterativeBST::new();
779 /// bst.insert(4);
780 /// bst.insert(6);
781 /// bst.insert(2);
782 /// bst.insert(7);
783 /// bst.insert(5);
784 /// bst.insert(3);
785 /// bst.insert(1);
786 ///
787 /// assert_eq!(bst.asc_order_vec(), vec![&1, &2, &3, &4, &5, &6, &7]);
788 /// ```
789 fn asc_order_vec(&self) -> Vec<&T> {
790 self.in_order_vec()
791 }
792
793 /// Returns references to the elements of the tree in the order of a **pre-order traversal.**
794 ///
795 /// # Example
796 ///
797 /// ```rust
798 /// use bst_rs::{BinarySearchTree, IterativeBST};
799 ///
800 /// // Given a tree that looks like:
801 /// // 4
802 /// // / \
803 /// // 2 6
804 /// // / \ / \
805 /// // 1 3 5 7
806 /// let mut bst = IterativeBST::new();
807 /// bst.insert(4);
808 /// bst.insert(6);
809 /// bst.insert(2);
810 /// bst.insert(7);
811 /// bst.insert(5);
812 /// bst.insert(3);
813 /// bst.insert(1);
814 ///
815 /// // The pre_order_vec is: [&4, &2, &1, &3, &6, &5, &7]
816 /// assert_eq!(bst.pre_order_vec(), vec![&4, &2, &1, &3, &6, &5, &7]);
817 /// ```
818 fn pre_order_vec(&self) -> Vec<&T> {
819 Node::iterative_pre_order_vec(&self.root)
820 }
821
822 /// Returns references to the elements of the tree in the order of an **in-order traversal.**
823 ///
824 /// # Important
825 ///
826 /// This is function is analogous to [IterativeBST::asc_order_vec()] as the underlying
827 /// behaviour is **_exactly the same_.**
828 ///
829 /// # Example
830 ///
831 /// ```rust
832 /// use bst_rs::{BinarySearchTree, IterativeBST};
833 ///
834 /// // Given a tree that looks like:
835 /// // 4
836 /// // / \
837 /// // 2 6
838 /// // / \ / \
839 /// // 1 3 5 7
840 /// let mut bst = IterativeBST::new();
841 /// bst.insert(4);
842 /// bst.insert(6);
843 /// bst.insert(2);
844 /// bst.insert(7);
845 /// bst.insert(5);
846 /// bst.insert(3);
847 /// bst.insert(1);
848 ///
849 /// // The in_order_vec is: [&1, &2, &3, &4, &5, &6, &7]
850 /// assert_eq!(bst.in_order_vec(), vec![&1, &2, &3, &4, &5, &6, &7]);
851 /// ```
852 fn in_order_vec(&self) -> Vec<&T> {
853 Node::iterative_in_order_vec(&self.root)
854 }
855
856 /// Returns references to the elements of the tree in the order of a **post-order traversal.**
857 ///
858 /// # Example
859 ///
860 /// ```rust
861 /// use bst_rs::{BinarySearchTree, IterativeBST};
862 ///
863 /// // Given a tree that looks like:
864 /// // 4
865 /// // / \
866 /// // 2 6
867 /// // / \ / \
868 /// // 1 3 5 7
869 /// let mut bst = IterativeBST::new();
870 /// bst.insert(4);
871 /// bst.insert(6);
872 /// bst.insert(2);
873 /// bst.insert(7);
874 /// bst.insert(5);
875 /// bst.insert(3);
876 /// bst.insert(1);
877 ///
878 /// // The post_order_vec is: [&1, &3, &2, &5, &7, &6, &4]
879 /// assert_eq!(bst.post_order_vec(), vec![&1, &3, &2, &5, &7, &6, &4]);
880 /// ```
881 fn post_order_vec(&self) -> Vec<&T> {
882 Node::iterative_post_order_vec(&self.root)
883 }
884
885 /// Returns references to the elements of the tree in the order of a **level-order traversal.**
886 ///
887 /// # Example
888 ///
889 /// ```rust
890 /// use bst_rs::{BinarySearchTree, IterativeBST};
891 ///
892 /// // Given a tree that looks like:
893 /// // 4
894 /// // / \
895 /// // 2 6
896 /// // / \ / \
897 /// // 1 3 5 7
898 /// let mut bst = IterativeBST::new();
899 /// bst.insert(4);
900 /// bst.insert(6);
901 /// bst.insert(2);
902 /// bst.insert(7);
903 /// bst.insert(5);
904 /// bst.insert(3);
905 /// bst.insert(1);
906 ///
907 /// // The level_order_vec is: [&4, &2, &6, &1, &3, &5, &7]
908 /// assert_eq!(bst.level_order_vec(), vec![&4, &2, &6, &1, &3, &5, &7]);
909 /// ```
910 fn level_order_vec(&self) -> Vec<&T> {
911 Node::iterative_level_order_vec(&self.root)
912 }
913
914 /// Returns an iterator over [IterativeBST::asc_order_vec()].
915 ///
916 /// # Important
917 ///
918 /// This is function is analogous to [IterativeBST::in_order_iter()] as the underlying
919 /// behaviour is **_exactly the same_.**
920 ///
921 /// # Example
922 ///
923 /// ```rust
924 /// use bst_rs::{BinarySearchTree, IterativeBST};
925 ///
926 /// let mut bst = IterativeBST::new();
927 /// bst.insert(3);
928 /// bst.insert(4);
929 /// bst.insert(5);
930 /// bst.insert(1);
931 /// bst.insert(2);
932 ///
933 /// let mut asc_order_iter = bst.asc_order_iter();
934 ///
935 /// assert_eq!(asc_order_iter.next(), Some(&1));
936 /// assert_eq!(asc_order_iter.next(), Some(&2));
937 /// assert_eq!(asc_order_iter.next(), Some(&3));
938 /// assert_eq!(asc_order_iter.next(), Some(&4));
939 /// assert_eq!(asc_order_iter.next(), Some(&5));
940 /// assert_eq!(asc_order_iter.next(), None);
941 /// ```
942 fn asc_order_iter(&self) -> IntoIter<&T> {
943 self.in_order_iter()
944 }
945
946 /// Returns an iterator over [IterativeBST::pre_order_vec()].
947 ///
948 /// # Example
949 ///
950 /// ```rust
951 /// use bst_rs::{BinarySearchTree, IterativeBST};
952 ///
953 /// let mut bst = IterativeBST::new();
954 /// bst.insert(3);
955 /// bst.insert(4);
956 /// bst.insert(5);
957 /// bst.insert(1);
958 /// bst.insert(2);
959 ///
960 /// let mut pre_order_iter = bst.pre_order_iter();
961 ///
962 /// assert_eq!(pre_order_iter.next(), Some(&3));
963 /// assert_eq!(pre_order_iter.next(), Some(&1));
964 /// assert_eq!(pre_order_iter.next(), Some(&2));
965 /// assert_eq!(pre_order_iter.next(), Some(&4));
966 /// assert_eq!(pre_order_iter.next(), Some(&5));
967 /// assert_eq!(pre_order_iter.next(), None);
968 /// ```
969 fn pre_order_iter(&self) -> IntoIter<&T> {
970 Node::iterative_pre_order_vec(&self.root).into_iter()
971 }
972
973 /// Returns an iterator over [IterativeBST::in_order_vec()].
974 ///
975 /// # Important
976 ///
977 /// This is function is analogous to [IterativeBST::asc_order_iter()] as the underlying
978 /// behaviour is **_exactly the same_.**
979 ///
980 /// # Example
981 ///
982 /// ```rust
983 /// use bst_rs::{BinarySearchTree, IterativeBST};
984 ///
985 /// let mut bst = IterativeBST::new();
986 /// bst.insert(3);
987 /// bst.insert(4);
988 /// bst.insert(5);
989 /// bst.insert(1);
990 /// bst.insert(2);
991 ///
992 /// let mut in_order_iter = bst.in_order_iter();
993 ///
994 /// assert_eq!(in_order_iter.next(), Some(&1));
995 /// assert_eq!(in_order_iter.next(), Some(&2));
996 /// assert_eq!(in_order_iter.next(), Some(&3));
997 /// assert_eq!(in_order_iter.next(), Some(&4));
998 /// assert_eq!(in_order_iter.next(), Some(&5));
999 /// assert_eq!(in_order_iter.next(), None);
1000 /// ```
1001 fn in_order_iter(&self) -> IntoIter<&T> {
1002 Node::iterative_in_order_vec(&self.root).into_iter()
1003 }
1004
1005 /// Returns an iterator over [IterativeBST::post_order_vec()].
1006 ///
1007 /// # Example
1008 ///
1009 /// ```rust
1010 /// use bst_rs::{BinarySearchTree, IterativeBST};
1011 ///
1012 /// let mut bst = IterativeBST::new();
1013 /// bst.insert(3);
1014 /// bst.insert(4);
1015 /// bst.insert(5);
1016 /// bst.insert(1);
1017 /// bst.insert(2);
1018 ///
1019 /// let mut post_order_iter = bst.post_order_iter();
1020 ///
1021 /// assert_eq!(post_order_iter.next(), Some(&2));
1022 /// assert_eq!(post_order_iter.next(), Some(&1));
1023 /// assert_eq!(post_order_iter.next(), Some(&5));
1024 /// assert_eq!(post_order_iter.next(), Some(&4));
1025 /// assert_eq!(post_order_iter.next(), Some(&3));
1026 /// assert_eq!(post_order_iter.next(), None);
1027 /// ```
1028 fn post_order_iter(&self) -> IntoIter<&T> {
1029 Node::iterative_post_order_vec(&self.root).into_iter()
1030 }
1031
1032 /// Returns an iterator over [IterativeBST::level_order_vec()].
1033 ///
1034 /// # Example
1035 ///
1036 /// ```rust
1037 /// use bst_rs::{BinarySearchTree, IterativeBST};
1038 ///
1039 /// let mut bst = IterativeBST::new();
1040 /// bst.insert(3);
1041 /// bst.insert(4);
1042 /// bst.insert(5);
1043 /// bst.insert(1);
1044 /// bst.insert(2);
1045 ///
1046 /// let mut level_order_iter = bst.level_order_iter();
1047 ///
1048 /// assert_eq!(level_order_iter.next(), Some(&3));
1049 /// assert_eq!(level_order_iter.next(), Some(&1));
1050 /// assert_eq!(level_order_iter.next(), Some(&4));
1051 /// assert_eq!(level_order_iter.next(), Some(&2));
1052 /// assert_eq!(level_order_iter.next(), Some(&5));
1053 /// assert_eq!(level_order_iter.next(), None);
1054 /// ```
1055 fn level_order_iter(&self) -> IntoIter<&T> {
1056 Node::iterative_level_order_vec(&self.root).into_iter()
1057 }
1058
1059 /// Returns [IterativeBST::asc_order_iter()] **AND** consumes the tree.
1060 ///
1061 /// # Important
1062 ///
1063 /// This is function is analogous to [IterativeBST::into_in_order_iter()] as the
1064 /// underlying behaviour is **_exactly the same_.**
1065 ///
1066 /// # Example
1067 ///
1068 /// ```rust
1069 /// use bst_rs::{BinarySearchTree, IterativeBST};
1070 ///
1071 /// let mut bst = IterativeBST::new();
1072 /// bst.insert(3);
1073 /// bst.insert(4);
1074 /// bst.insert(5);
1075 /// bst.insert(1);
1076 /// bst.insert(2);
1077 ///
1078 /// let mut into_asc_order_iter = bst.into_asc_order_iter();
1079 ///
1080 /// assert_eq!(into_asc_order_iter.next(), Some(1));
1081 /// assert_eq!(into_asc_order_iter.next(), Some(2));
1082 /// assert_eq!(into_asc_order_iter.next(), Some(3));
1083 /// assert_eq!(into_asc_order_iter.next(), Some(4));
1084 /// assert_eq!(into_asc_order_iter.next(), Some(5));
1085 /// assert_eq!(into_asc_order_iter.next(), None);
1086 ///
1087 /// // bst.insert(10); -> COMPILE ERROR
1088 /// ```
1089 fn into_asc_order_iter(self) -> IntoIter<T> {
1090 self.into_in_order_iter()
1091 }
1092
1093 /// Returns [IterativeBST::pre_order_iter()] **AND** consumes the tree.
1094 ///
1095 /// # Example
1096 ///
1097 /// ```rust
1098 /// use bst_rs::{BinarySearchTree, IterativeBST};
1099 ///
1100 /// let mut bst = IterativeBST::new();
1101 /// bst.insert(3);
1102 /// bst.insert(4);
1103 /// bst.insert(5);
1104 /// bst.insert(1);
1105 /// bst.insert(2);
1106 ///
1107 /// let mut into_pre_order_iter = bst.into_pre_order_iter();
1108 ///
1109 /// assert_eq!(into_pre_order_iter.next(), Some(3));
1110 /// assert_eq!(into_pre_order_iter.next(), Some(1));
1111 /// assert_eq!(into_pre_order_iter.next(), Some(2));
1112 /// assert_eq!(into_pre_order_iter.next(), Some(4));
1113 /// assert_eq!(into_pre_order_iter.next(), Some(5));
1114 /// assert_eq!(into_pre_order_iter.next(), None);
1115 ///
1116 /// // bst.insert(10); -> COMPILE ERROR
1117 /// ```
1118 fn into_pre_order_iter(self) -> IntoIter<T> {
1119 Node::iterative_consume_pre_order_vec(self.root).into_iter()
1120 }
1121
1122 /// Returns [IterativeBST::in_order_iter()] **AND** consumes the tree.
1123 ///
1124 /// # Important
1125 ///
1126 /// This is function is analogous to [IterativeBST::asc_order_iter()] as the
1127 /// underlying behaviour is **_exactly the same_.**
1128 ///
1129 /// # Example
1130 ///
1131 /// ```rust
1132 /// use bst_rs::{BinarySearchTree, IterativeBST};
1133 ///
1134 /// let mut bst = IterativeBST::new();
1135 /// bst.insert(3);
1136 /// bst.insert(4);
1137 /// bst.insert(5);
1138 /// bst.insert(1);
1139 /// bst.insert(2);
1140 ///
1141 /// let mut into_in_order_iter = bst.into_in_order_iter();
1142 ///
1143 /// assert_eq!(into_in_order_iter.next(), Some(1));
1144 /// assert_eq!(into_in_order_iter.next(), Some(2));
1145 /// assert_eq!(into_in_order_iter.next(), Some(3));
1146 /// assert_eq!(into_in_order_iter.next(), Some(4));
1147 /// assert_eq!(into_in_order_iter.next(), Some(5));
1148 /// assert_eq!(into_in_order_iter.next(), None);
1149 ///
1150 /// // bst.insert(10); -> COMPILE ERROR
1151 /// ```
1152 fn into_in_order_iter(self) -> IntoIter<T> {
1153 Node::iterative_consume_in_order_vec(self.root).into_iter()
1154 }
1155
1156 /// Returns [IterativeBST::post_order_iter()] **AND** consumes the tree.
1157 ///
1158 /// # Example
1159 ///
1160 /// ```rust
1161 /// use bst_rs::{BinarySearchTree, IterativeBST};
1162 ///
1163 /// let mut bst = IterativeBST::new();
1164 /// bst.insert(3);
1165 /// bst.insert(4);
1166 /// bst.insert(5);
1167 /// bst.insert(1);
1168 /// bst.insert(2);
1169 ///
1170 /// let mut into_post_order_iter = bst.into_post_order_iter();
1171 ///
1172 /// assert_eq!(into_post_order_iter.next(), Some(2));
1173 /// assert_eq!(into_post_order_iter.next(), Some(1));
1174 /// assert_eq!(into_post_order_iter.next(), Some(5));
1175 /// assert_eq!(into_post_order_iter.next(), Some(4));
1176 /// assert_eq!(into_post_order_iter.next(), Some(3));
1177 /// assert_eq!(into_post_order_iter.next(), None);
1178 ///
1179 /// // bst.insert(10); -> COMPILE ERROR
1180 /// ```
1181 fn into_post_order_iter(self) -> IntoIter<T> {
1182 Node::iterative_consume_post_order_vec(self.root).into_iter()
1183 }
1184
1185 /// Returns [IterativeBST::level_order_iter()] **AND** consumes the tree.
1186 ///
1187 /// # Example
1188 ///
1189 /// ```rust
1190 /// use bst_rs::{BinarySearchTree, IterativeBST};
1191 ///
1192 /// let mut bst = IterativeBST::new();
1193 /// bst.insert(3);
1194 /// bst.insert(4);
1195 /// bst.insert(5);
1196 /// bst.insert(1);
1197 /// bst.insert(2);
1198 ///
1199 /// let mut into_level_order_iter = bst.into_level_order_iter();
1200 ///
1201 /// assert_eq!(into_level_order_iter.next(), Some(3));
1202 /// assert_eq!(into_level_order_iter.next(), Some(1));
1203 /// assert_eq!(into_level_order_iter.next(), Some(4));
1204 /// assert_eq!(into_level_order_iter.next(), Some(2));
1205 /// assert_eq!(into_level_order_iter.next(), Some(5));
1206 /// assert_eq!(into_level_order_iter.next(), None);
1207 ///
1208 /// // bst.insert(10); -> COMPILE ERROR
1209 /// ```
1210 fn into_level_order_iter(self) -> IntoIter<T> {
1211 Node::iterative_consume_level_order_vec(self.root).into_iter()
1212 }
1213}
1214
1215impl<T: Ord> RecursiveBST<T> {
1216 /// Creates an empty `RecursiveBST<T>`
1217 ///
1218 /// No nodes are allocated on the heap yet
1219 ///
1220 /// # Examples
1221 ///
1222 /// ```rust
1223 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1224 ///
1225 /// // Empty tree is created
1226 /// let mut bst: RecursiveBST<i32> = RecursiveBST::new();
1227 /// assert!(bst.is_empty())
1228 /// ```
1229 pub fn new() -> RecursiveBST<T> {
1230 RecursiveBST {
1231 root: None,
1232 size: 0,
1233 }
1234 }
1235}
1236
1237impl<T: Ord> Default for RecursiveBST<T> {
1238 /// Creates an empty `RecursiveBST<T>`
1239 fn default() -> RecursiveBST<T> {
1240 RecursiveBST::new()
1241 }
1242}
1243
1244impl<T: Ord> PartialEq for RecursiveBST<T> {
1245 fn eq(&self, other: &Self) -> bool {
1246 self.asc_order_vec() == other.asc_order_vec()
1247 }
1248}
1249
1250impl<T: Ord> Extend<T> for RecursiveBST<T> {
1251 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1252 for value in iter.into_iter() {
1253 self.insert(value)
1254 }
1255 }
1256}
1257
1258impl<T: Ord> FromIterator<T> for RecursiveBST<T> {
1259 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1260 let mut bst = RecursiveBST::new();
1261 bst.extend(iter);
1262 bst
1263 }
1264}
1265
1266impl<T: Ord> From<Vec<T>> for RecursiveBST<T> {
1267 fn from(vec: Vec<T>) -> Self {
1268 let mut bst = RecursiveBST::new();
1269 for value in vec.into_iter() {
1270 bst.insert(value);
1271 }
1272 bst
1273 }
1274}
1275
1276impl<T: Ord + Clone> From<&[T]> for RecursiveBST<T> {
1277 fn from(slice: &[T]) -> Self {
1278 let mut bst = RecursiveBST::new();
1279 for value in slice {
1280 bst.insert((*value).clone());
1281 }
1282 bst
1283 }
1284}
1285
1286impl<T: Ord + Clone> Clone for RecursiveBST<T> {
1287 fn clone(&self) -> Self {
1288 let mut bst = RecursiveBST::new();
1289
1290 for value in self.in_order_iter() {
1291 bst.insert((*value).clone());
1292 }
1293
1294 bst
1295 }
1296}
1297
1298impl<T: Ord + Debug> Display for RecursiveBST<T> {
1299 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
1300 write!(f, "{:?}", self.asc_order_vec())
1301 }
1302}
1303
1304impl<T: Ord> BinarySearchTree<T> for RecursiveBST<T> {
1305 /// Returns the total **number of nodes** within the tree.
1306 ///
1307 /// # Example
1308 ///
1309 /// ```rust
1310 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1311 ///
1312 /// let mut bst = RecursiveBST::new();
1313 /// bst.insert(5);
1314 /// bst.insert(10);
1315 /// bst.insert(3);
1316 ///
1317 /// assert_eq!(bst.size(), 3);
1318 /// ```
1319 fn size(&self) -> usize {
1320 self.size
1321 }
1322
1323 /// Returns `true` if the binary search tree contains no nodes.
1324 ///
1325 /// # Examples
1326 ///
1327 /// ```rust
1328 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1329 ///
1330 /// let mut bst: RecursiveBST<i32> = RecursiveBST::new();
1331 /// assert!(bst.is_empty());
1332 /// ```
1333 fn is_empty(&self) -> bool {
1334 self.size == 0
1335 }
1336
1337 /// Returns `true` if the binary search tree contains one or more nodes.
1338 ///
1339 /// # Example
1340 ///
1341 /// ```rust
1342 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1343 ///
1344 /// let mut bst = RecursiveBST::new();
1345 /// assert!(bst.is_empty());
1346 ///
1347 /// bst.insert(2);
1348 ///
1349 /// assert!(bst.is_not_empty());
1350 /// ```
1351 fn is_not_empty(&self) -> bool {
1352 self.size != 0
1353 }
1354
1355 /// Inserts given value as a node.
1356 ///
1357 /// **Duplicate values are _not allowed_**.
1358 ///
1359 /// # Example
1360 ///
1361 /// ```rust
1362 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1363 ///
1364 /// let mut bst = RecursiveBST::new();
1365 ///
1366 /// bst.insert(10);
1367 /// bst.insert(10); // Element is not inserted
1368 /// bst.insert(5);
1369 /// bst.insert(2);
1370 /// bst.insert(15);
1371 /// bst.insert(25);
1372 ///
1373 /// assert_eq!(bst.size(), 5);
1374 /// ```
1375 fn insert(&mut self, value: T) {
1376 match self.root {
1377 None => {
1378 self.root = Some(Box::from(Node::new(value)));
1379 self.size += 1;
1380 }
1381 Some(ref mut node) => {
1382 if node.recursive_insert(value).is_ok() {
1383 self.size += 1;
1384 }
1385 }
1386 }
1387 }
1388
1389 /// Returns `true` if the binary search tree contains an element with the given value.
1390 ///
1391 /// # Example
1392 ///
1393 /// ```rust
1394 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1395 ///
1396 /// let mut bst = RecursiveBST::new();
1397 /// bst.insert(5);
1398 /// bst.insert(2);
1399 /// bst.insert(7);
1400 ///
1401 /// assert!(bst.contains(&5));
1402 /// assert!(!bst.contains(&10));
1403 /// ```
1404 fn contains(&self, value: &T) -> bool {
1405 match self.root {
1406 None => false,
1407 Some(ref node) => node.recursive_contains(value),
1408 }
1409 }
1410
1411 /// Removes the given value.
1412 ///
1413 /// Tree will not be modified if trying to remove element that does not exist.
1414 ///
1415 /// # Example
1416 ///
1417 /// ```rust
1418 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1419 ///
1420 /// let mut bst = RecursiveBST::new();
1421 /// bst.insert(5);
1422 /// bst.insert(2);
1423 /// bst.insert(7);
1424 /// assert_eq!(bst.size(), 3);
1425 ///
1426 /// bst.remove(&5);
1427 /// bst.remove(&10); // Element is not removed
1428 /// assert_eq!(bst.size(), 2);
1429 /// ```
1430 fn remove(&mut self, value: &T) {
1431 if Node::recursive_remove(&mut self.root, value).is_ok() {
1432 self.size -= 1;
1433 }
1434 }
1435
1436 /// Returns a reference to the element or `None` if element does not exist.
1437 ///
1438 /// # Example
1439 ///
1440 /// ```rust
1441 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1442 ///
1443 /// let mut bst = RecursiveBST::new();
1444 /// bst.insert(5);
1445 /// bst.insert(2);
1446 /// bst.insert(7);
1447 ///
1448 /// assert_eq!(bst.retrieve(&5), Some(&5));
1449 /// assert_eq!(bst.retrieve(&10), None);
1450 /// ```
1451 fn retrieve(&self, value: &T) -> Option<&T> {
1452 match self.root {
1453 None => None,
1454 Some(ref node) => node.recursive_retrieve(value),
1455 }
1456 }
1457
1458 /// Returns a mutable reference to the element (see [RecursiveBST::retrieve()])
1459 /// or `None` if element does not exist.
1460 ///
1461 /// # Example
1462 ///
1463 /// ```rust
1464 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1465 ///
1466 /// let mut bst = RecursiveBST::new();
1467 /// bst.insert(10);
1468 /// bst.insert(5);
1469 ///
1470 /// let optional_retrieved_value_as_mut = bst.retrieve_as_mut(&5);
1471 /// assert_eq!(optional_retrieved_value_as_mut, Some(&mut 5));
1472 ///
1473 /// let mut retrieved_value = optional_retrieved_value_as_mut.unwrap();
1474 /// *retrieved_value = 2; // Change value inside tree to '2'
1475 ///
1476 /// assert_eq!(bst.retrieve_as_mut(&5), None); // 5 does not exist anymore
1477 /// assert_eq!(bst.retrieve_as_mut(&2), Some(&mut 2));
1478 /// ```
1479 fn retrieve_as_mut(&mut self, value: &T) -> Option<&mut T> {
1480 match self.root {
1481 None => None,
1482 Some(ref mut node) => node.recursive_retrieve_as_mut(value),
1483 }
1484 }
1485
1486 /// Returns the **height** or `None` if tree is empty.
1487 ///
1488 /// The height is the number of edges between the root and it's furthest leaf node.
1489 ///
1490 /// # Example
1491 ///
1492 /// ```rust
1493 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1494 ///
1495 /// // Given a tree that looks like:
1496 /// // 4
1497 /// // / \
1498 /// // 2 6
1499 /// // / \ / \
1500 /// // 1 3 5 7
1501 /// let mut bst = RecursiveBST::new();
1502 /// assert_eq!(bst.height(), None);
1503 ///
1504 /// bst.insert(4);
1505 /// bst.insert(6);
1506 /// bst.insert(2);
1507 /// bst.insert(7);
1508 /// bst.insert(5);
1509 /// bst.insert(3);
1510 /// bst.insert(1);
1511 ///
1512 /// // The height is 2.
1513 /// assert_eq!(bst.height(), Some(2));
1514 /// ```
1515 fn height(&self) -> Option<isize> {
1516 self.root
1517 .as_ref()
1518 .map(|_| Node::recursive_height(&self.root))
1519 }
1520
1521 /// Returns a reference to the minimum element of the tree or `None` if tree is empty.
1522 ///
1523 /// # Example
1524 ///
1525 /// ```rust
1526 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1527 ///
1528 /// let mut bst = RecursiveBST::new();
1529 /// assert_eq!(bst.min(), None);
1530 ///
1531 /// bst.insert(5);
1532 /// bst.insert(2);
1533 /// bst.insert(10);
1534 ///
1535 /// assert_eq!(bst.min(), Some(&2));
1536 /// ```
1537 fn min(&self) -> Option<&T> {
1538 match self.root {
1539 None => None,
1540 Some(ref node) => node.recursive_min(),
1541 }
1542 }
1543
1544 /// Returns a reference to the maximum element of the tree or `None` if tree is empty.
1545 ///
1546 /// # Example
1547 ///
1548 /// ```rust
1549 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1550 ///
1551 /// let mut bst = RecursiveBST::new();
1552 /// assert_eq!(bst.max(), None);
1553 ///
1554 /// bst.insert(5);
1555 /// bst.insert(2);
1556 /// bst.insert(10);
1557 ///
1558 /// assert_eq!(bst.max(), Some(&10));
1559 /// ```
1560 fn max(&self) -> Option<&T> {
1561 match self.root {
1562 None => None,
1563 Some(ref node) => node.recursive_max(),
1564 }
1565 }
1566
1567 /// Removes and returns the minimum element from the tree or `None` if tree is empty.
1568 ///
1569 /// # Example
1570 ///
1571 /// ```rust
1572 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1573 ///
1574 /// let mut bst = RecursiveBST::new();
1575 /// assert_eq!(bst.remove_min(), None);
1576 ///
1577 /// bst.insert(2);
1578 /// bst.insert(5);
1579 /// bst.insert(10);
1580 ///
1581 /// assert_eq!(bst.size(), 3);
1582 /// assert_eq!(bst.remove_min(), Some(2));
1583 /// assert_eq!(bst.size(), 2);
1584 /// ```
1585 fn remove_min(&mut self) -> Option<T> {
1586 let removed_min = match self.root {
1587 None => None,
1588 Some(_) => Node::recursive_remove_min(&mut self.root),
1589 };
1590
1591 if removed_min.is_some() {
1592 self.size -= 1;
1593 }
1594
1595 removed_min
1596 }
1597
1598 /// Removes and returns the maximum element from the tree or `None` if tree is empty.
1599 ///
1600 /// # Example
1601 ///
1602 /// ```rust
1603 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1604 ///
1605 /// let mut bst = RecursiveBST::new();
1606 /// assert_eq!(bst.remove_max(), None);
1607 ///
1608 /// bst.insert(2);
1609 /// bst.insert(5);
1610 /// bst.insert(10);
1611 ///
1612 /// assert_eq!(bst.size(), 3);
1613 /// assert_eq!(bst.remove_max(), Some(10));
1614 /// assert_eq!(bst.size(), 2);
1615 /// ```
1616 fn remove_max(&mut self) -> Option<T> {
1617 let removed_max = match self.root {
1618 None => None,
1619 Some(_) => Node::recursive_remove_max(&mut self.root),
1620 };
1621
1622 if removed_max.is_some() {
1623 self.size -= 1;
1624 }
1625
1626 removed_max
1627 }
1628
1629 /// Returns references to the elements of the tree in **ascending order.**
1630 ///
1631 /// # Important
1632 ///
1633 /// This is function is analogous to [RecursiveBST::in_order_vec()] as the underlying
1634 /// behaviour is **_exactly the same_.**
1635 ///
1636 /// # Example
1637 ///
1638 /// ```rust
1639 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1640 ///
1641 /// let mut bst = RecursiveBST::new();
1642 /// bst.insert(4);
1643 /// bst.insert(6);
1644 /// bst.insert(2);
1645 /// bst.insert(7);
1646 /// bst.insert(5);
1647 /// bst.insert(3);
1648 /// bst.insert(1);
1649 ///
1650 /// assert_eq!(bst.asc_order_vec(), vec![&1, &2, &3, &4, &5, &6, &7]);
1651 /// ```
1652 fn asc_order_vec(&self) -> Vec<&T> {
1653 let mut elements: Vec<&T> = Vec::new();
1654 Node::recursive_in_order_vec(&self.root, &mut elements);
1655 elements
1656 }
1657
1658 /// Returns references to the elements of the tree in the order of a **pre-order traversal.**
1659 ///
1660 /// # Example
1661 ///
1662 /// ```rust
1663 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1664 ///
1665 /// // Given a tree that looks like:
1666 /// // 4
1667 /// // / \
1668 /// // 2 6
1669 /// // / \ / \
1670 /// // 1 3 5 7
1671 /// let mut bst = RecursiveBST::new();
1672 /// bst.insert(4);
1673 /// bst.insert(6);
1674 /// bst.insert(2);
1675 /// bst.insert(7);
1676 /// bst.insert(5);
1677 /// bst.insert(3);
1678 /// bst.insert(1);
1679 ///
1680 /// // The pre_order_vec is: [&4, &2, &1, &3, &6, &5, &7]
1681 /// assert_eq!(bst.pre_order_vec(), vec![&4, &2, &1, &3, &6, &5, &7]);
1682 /// ```
1683 fn pre_order_vec(&self) -> Vec<&T> {
1684 let mut elements: Vec<&T> = Vec::new();
1685 Node::recursive_pre_order_vec(&self.root, &mut elements);
1686 elements
1687 }
1688
1689 /// Returns references to the elements of the tree in the order of an **in-order traversal.**
1690 ///
1691 /// # Important
1692 ///
1693 /// This is function is analogous to [RecursiveBST::asc_order_vec()] as the underlying
1694 /// behaviour is **_exactly the same_.**
1695 ///
1696 /// # Example
1697 ///
1698 /// ```rust
1699 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1700 ///
1701 /// // Given a tree that looks like:
1702 /// // 4
1703 /// // / \
1704 /// // 2 6
1705 /// // / \ / \
1706 /// // 1 3 5 7
1707 /// let mut bst = RecursiveBST::new();
1708 /// bst.insert(4);
1709 /// bst.insert(6);
1710 /// bst.insert(2);
1711 /// bst.insert(7);
1712 /// bst.insert(5);
1713 /// bst.insert(3);
1714 /// bst.insert(1);
1715 ///
1716 /// // The in_order_vec is: [&1, &2, &3, &4, &5, &6, &7]
1717 /// assert_eq!(bst.in_order_vec(), vec![&1, &2, &3, &4, &5, &6, &7]);
1718 /// ```
1719 fn in_order_vec(&self) -> Vec<&T> {
1720 let mut elements: Vec<&T> = Vec::new();
1721 Node::recursive_in_order_vec(&self.root, &mut elements);
1722 elements
1723 }
1724
1725 /// Returns references to the elements of the tree in the order of a **post-order traversal.**
1726 ///
1727 /// # Example
1728 ///
1729 /// ```rust
1730 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1731 ///
1732 /// // Given a tree that looks like:
1733 /// // 4
1734 /// // / \
1735 /// // 2 6
1736 /// // / \ / \
1737 /// // 1 3 5 7
1738 /// let mut bst = RecursiveBST::new();
1739 /// bst.insert(4);
1740 /// bst.insert(6);
1741 /// bst.insert(2);
1742 /// bst.insert(7);
1743 /// bst.insert(5);
1744 /// bst.insert(3);
1745 /// bst.insert(1);
1746 ///
1747 /// // The post_order_vec is: [&1, &3, &2, &5, &7, &6, &4]
1748 /// assert_eq!(bst.post_order_vec(), vec![&1, &3, &2, &5, &7, &6, &4]);
1749 /// ```
1750 fn post_order_vec(&self) -> Vec<&T> {
1751 let mut elements: Vec<&T> = Vec::new();
1752 Node::recursive_post_order_vec(&self.root, &mut elements);
1753 elements
1754 }
1755
1756 /// Returns references to the elements of the tree in the order of a **level-order traversal.**
1757 ///
1758 /// # Example
1759 ///
1760 /// ```rust
1761 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1762 ///
1763 /// // Given a tree that looks like:
1764 /// // 4
1765 /// // / \
1766 /// // 2 6
1767 /// // / \ / \
1768 /// // 1 3 5 7
1769 /// let mut bst = RecursiveBST::new();
1770 /// bst.insert(4);
1771 /// bst.insert(6);
1772 /// bst.insert(2);
1773 /// bst.insert(7);
1774 /// bst.insert(5);
1775 /// bst.insert(3);
1776 /// bst.insert(1);
1777 ///
1778 /// // The level_order_vec is: [&4, &2, &6, &1, &3, &5, &7]
1779 /// assert_eq!(bst.level_order_vec(), vec![&4, &2, &6, &1, &3, &5, &7]);
1780 /// ```
1781 fn level_order_vec(&self) -> Vec<&T> {
1782 let mut elements: Vec<&T> = Vec::new();
1783 Node::recursive_level_order_vec(&self.root, &mut elements);
1784 elements
1785 }
1786
1787 /// Returns an iterator over [RecursiveBST::asc_order_vec()].
1788 ///
1789 /// # Important
1790 ///
1791 /// This is function is analogous to [RecursiveBST::in_order_iter()] as the underlying
1792 /// behaviour is **_exactly the same_.**
1793 ///
1794 /// # Example
1795 ///
1796 /// ```rust
1797 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1798 ///
1799 /// let mut bst = RecursiveBST::new();
1800 /// bst.insert(3);
1801 /// bst.insert(4);
1802 /// bst.insert(5);
1803 /// bst.insert(1);
1804 /// bst.insert(2);
1805 ///
1806 /// let mut asc_order_iter = bst.asc_order_iter();
1807 ///
1808 /// assert_eq!(asc_order_iter.next(), Some(&1));
1809 /// assert_eq!(asc_order_iter.next(), Some(&2));
1810 /// assert_eq!(asc_order_iter.next(), Some(&3));
1811 /// assert_eq!(asc_order_iter.next(), Some(&4));
1812 /// assert_eq!(asc_order_iter.next(), Some(&5));
1813 /// assert_eq!(asc_order_iter.next(), None);
1814 /// ```
1815 fn asc_order_iter(&self) -> IntoIter<&T> {
1816 let mut elements = Vec::new();
1817 Node::recursive_in_order_vec(&self.root, &mut elements);
1818 elements.into_iter()
1819 }
1820
1821 /// Returns an iterator over [RecursiveBST::pre_order_vec()].
1822 ///
1823 /// # Example
1824 ///
1825 /// ```rust
1826 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1827 ///
1828 /// let mut bst = RecursiveBST::new();
1829 /// bst.insert(3);
1830 /// bst.insert(4);
1831 /// bst.insert(5);
1832 /// bst.insert(1);
1833 /// bst.insert(2);
1834 ///
1835 /// let mut pre_order_iter = bst.pre_order_iter();
1836 ///
1837 /// assert_eq!(pre_order_iter.next(), Some(&3));
1838 /// assert_eq!(pre_order_iter.next(), Some(&1));
1839 /// assert_eq!(pre_order_iter.next(), Some(&2));
1840 /// assert_eq!(pre_order_iter.next(), Some(&4));
1841 /// assert_eq!(pre_order_iter.next(), Some(&5));
1842 /// assert_eq!(pre_order_iter.next(), None);
1843 /// ```
1844 fn pre_order_iter(&self) -> IntoIter<&T> {
1845 let mut elements: Vec<&T> = Vec::new();
1846 Node::recursive_pre_order_vec(&self.root, &mut elements);
1847 elements.into_iter()
1848 }
1849
1850 /// Returns an iterator over [RecursiveBST::in_order_vec()].
1851 ///
1852 /// # Important
1853 ///
1854 /// This is function is analogous to [RecursiveBST::asc_order_iter()] as the underlying
1855 /// behaviour is **_exactly the same_.**
1856 ///
1857 /// # Example
1858 ///
1859 /// ```rust
1860 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1861 ///
1862 /// let mut bst = RecursiveBST::new();
1863 /// bst.insert(3);
1864 /// bst.insert(4);
1865 /// bst.insert(5);
1866 /// bst.insert(1);
1867 /// bst.insert(2);
1868 ///
1869 /// let mut in_order_iter = bst.in_order_iter();
1870 ///
1871 /// assert_eq!(in_order_iter.next(), Some(&1));
1872 /// assert_eq!(in_order_iter.next(), Some(&2));
1873 /// assert_eq!(in_order_iter.next(), Some(&3));
1874 /// assert_eq!(in_order_iter.next(), Some(&4));
1875 /// assert_eq!(in_order_iter.next(), Some(&5));
1876 /// assert_eq!(in_order_iter.next(), None);
1877 /// ```
1878 fn in_order_iter(&self) -> IntoIter<&T> {
1879 let mut elements: Vec<&T> = Vec::new();
1880 Node::recursive_in_order_vec(&self.root, &mut elements);
1881 elements.into_iter()
1882 }
1883
1884 /// Returns an iterator over [RecursiveBST::post_order_vec()].
1885 ///
1886 /// # Example
1887 ///
1888 /// ```rust
1889 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1890 ///
1891 /// let mut bst = RecursiveBST::new();
1892 /// bst.insert(3);
1893 /// bst.insert(4);
1894 /// bst.insert(5);
1895 /// bst.insert(1);
1896 /// bst.insert(2);
1897 ///
1898 /// let mut post_order_iter = bst.post_order_iter();
1899 ///
1900 /// assert_eq!(post_order_iter.next(), Some(&2));
1901 /// assert_eq!(post_order_iter.next(), Some(&1));
1902 /// assert_eq!(post_order_iter.next(), Some(&5));
1903 /// assert_eq!(post_order_iter.next(), Some(&4));
1904 /// assert_eq!(post_order_iter.next(), Some(&3));
1905 /// assert_eq!(post_order_iter.next(), None);
1906 /// ```
1907 fn post_order_iter(&self) -> IntoIter<&T> {
1908 let mut elements: Vec<&T> = Vec::new();
1909 Node::recursive_post_order_vec(&self.root, &mut elements);
1910 elements.into_iter()
1911 }
1912
1913 /// Returns an iterator over [RecursiveBST::level_order_vec()].
1914 ///
1915 /// # Example
1916 ///
1917 /// ```rust
1918 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1919 ///
1920 /// let mut bst = RecursiveBST::new();
1921 /// bst.insert(3);
1922 /// bst.insert(4);
1923 /// bst.insert(5);
1924 /// bst.insert(1);
1925 /// bst.insert(2);
1926 ///
1927 /// let mut level_order_iter = bst.level_order_iter();
1928 ///
1929 /// assert_eq!(level_order_iter.next(), Some(&3));
1930 /// assert_eq!(level_order_iter.next(), Some(&1));
1931 /// assert_eq!(level_order_iter.next(), Some(&4));
1932 /// assert_eq!(level_order_iter.next(), Some(&2));
1933 /// assert_eq!(level_order_iter.next(), Some(&5));
1934 /// assert_eq!(level_order_iter.next(), None);
1935 /// ```
1936 fn level_order_iter(&self) -> IntoIter<&T> {
1937 let mut elements: Vec<&T> = Vec::new();
1938 Node::recursive_level_order_vec(&self.root, &mut elements);
1939 elements.into_iter()
1940 }
1941
1942 /// Returns [RecursiveBST::asc_order_iter()] **AND** consumes the tree.
1943 ///
1944 /// # Important
1945 ///
1946 /// This is function is analogous to [RecursiveBST::into_in_order_iter()] as the
1947 /// underlying behaviour is **_exactly the same_.**
1948 ///
1949 /// # Example
1950 ///
1951 /// ```rust
1952 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1953 ///
1954 /// let mut bst = RecursiveBST::new();
1955 /// bst.insert(3);
1956 /// bst.insert(4);
1957 /// bst.insert(5);
1958 /// bst.insert(1);
1959 /// bst.insert(2);
1960 ///
1961 /// let mut into_asc_order_iter = bst.into_asc_order_iter();
1962 ///
1963 /// assert_eq!(into_asc_order_iter.next(), Some(1));
1964 /// assert_eq!(into_asc_order_iter.next(), Some(2));
1965 /// assert_eq!(into_asc_order_iter.next(), Some(3));
1966 /// assert_eq!(into_asc_order_iter.next(), Some(4));
1967 /// assert_eq!(into_asc_order_iter.next(), Some(5));
1968 /// assert_eq!(into_asc_order_iter.next(), None);
1969 ///
1970 /// // bst.insert(10); -> COMPILE ERROR
1971 /// ```
1972 fn into_asc_order_iter(self) -> IntoIter<T> {
1973 self.into_in_order_iter()
1974 }
1975
1976 /// Returns [RecursiveBST::pre_order_iter()] **AND** consumes the tree.
1977 ///
1978 /// # Example
1979 ///
1980 /// ```rust
1981 /// use bst_rs::{BinarySearchTree, RecursiveBST};
1982 ///
1983 /// let mut bst = RecursiveBST::new();
1984 /// bst.insert(3);
1985 /// bst.insert(4);
1986 /// bst.insert(5);
1987 /// bst.insert(1);
1988 /// bst.insert(2);
1989 ///
1990 /// let mut into_pre_order_iter = bst.into_pre_order_iter();
1991 ///
1992 /// assert_eq!(into_pre_order_iter.next(), Some(3));
1993 /// assert_eq!(into_pre_order_iter.next(), Some(1));
1994 /// assert_eq!(into_pre_order_iter.next(), Some(2));
1995 /// assert_eq!(into_pre_order_iter.next(), Some(4));
1996 /// assert_eq!(into_pre_order_iter.next(), Some(5));
1997 /// assert_eq!(into_pre_order_iter.next(), None);
1998 ///
1999 /// // bst.insert(10); -> COMPILE ERROR
2000 /// ```
2001 fn into_pre_order_iter(self) -> IntoIter<T> {
2002 let mut elements = Vec::new();
2003 Node::recursive_consume_pre_order_vec(self.root, &mut elements);
2004 elements.into_iter()
2005 }
2006
2007 /// Returns [RecursiveBST::in_order_iter()] **AND** consumes the tree.
2008 ///
2009 /// # Important
2010 ///
2011 /// This is function is analogous to [RecursiveBST::asc_order_iter()] as the
2012 /// underlying behaviour is **_exactly the same_.**
2013 ///
2014 /// # Example
2015 ///
2016 /// ```rust
2017 /// use bst_rs::{BinarySearchTree, RecursiveBST};
2018 ///
2019 /// let mut bst = RecursiveBST::new();
2020 /// bst.insert(3);
2021 /// bst.insert(4);
2022 /// bst.insert(5);
2023 /// bst.insert(1);
2024 /// bst.insert(2);
2025 ///
2026 /// let mut into_in_order_iter = bst.into_in_order_iter();
2027 ///
2028 /// assert_eq!(into_in_order_iter.next(), Some(1));
2029 /// assert_eq!(into_in_order_iter.next(), Some(2));
2030 /// assert_eq!(into_in_order_iter.next(), Some(3));
2031 /// assert_eq!(into_in_order_iter.next(), Some(4));
2032 /// assert_eq!(into_in_order_iter.next(), Some(5));
2033 /// assert_eq!(into_in_order_iter.next(), None);
2034 ///
2035 /// // bst.insert(10); -> COMPILE ERROR
2036 /// ```
2037 fn into_in_order_iter(self) -> IntoIter<T> {
2038 let mut elements = Vec::new();
2039 Node::recursive_consume_in_order_vec(self.root, &mut elements);
2040 elements.into_iter()
2041 }
2042
2043 /// Returns [RecursiveBST::post_order_iter()] **AND** consumes the tree.
2044 ///
2045 /// # Example
2046 ///
2047 /// ```rust
2048 /// use bst_rs::{BinarySearchTree, RecursiveBST};
2049 ///
2050 /// let mut bst = RecursiveBST::new();
2051 /// bst.insert(3);
2052 /// bst.insert(4);
2053 /// bst.insert(5);
2054 /// bst.insert(1);
2055 /// bst.insert(2);
2056 ///
2057 /// let mut into_post_order_iter = bst.into_post_order_iter();
2058 ///
2059 /// assert_eq!(into_post_order_iter.next(), Some(2));
2060 /// assert_eq!(into_post_order_iter.next(), Some(1));
2061 /// assert_eq!(into_post_order_iter.next(), Some(5));
2062 /// assert_eq!(into_post_order_iter.next(), Some(4));
2063 /// assert_eq!(into_post_order_iter.next(), Some(3));
2064 /// assert_eq!(into_post_order_iter.next(), None);
2065 ///
2066 /// // bst.insert(10); -> COMPILE ERROR
2067 /// ```
2068 fn into_post_order_iter(self) -> IntoIter<T> {
2069 let mut elements = Vec::new();
2070 Node::recursive_consume_post_order_vec(self.root, &mut elements);
2071 elements.into_iter()
2072 }
2073
2074 /// Returns [RecursiveBST::level_order_iter()] **AND** consumes the tree.
2075 ///
2076 /// # Example
2077 ///
2078 /// ```rust
2079 /// use bst_rs::{BinarySearchTree, RecursiveBST};
2080 ///
2081 /// let mut bst = RecursiveBST::new();
2082 /// bst.insert(3);
2083 /// bst.insert(4);
2084 /// bst.insert(5);
2085 /// bst.insert(1);
2086 /// bst.insert(2);
2087 ///
2088 /// let mut into_level_order_iter = bst.into_level_order_iter();
2089 ///
2090 /// assert_eq!(into_level_order_iter.next(), Some(3));
2091 /// assert_eq!(into_level_order_iter.next(), Some(1));
2092 /// assert_eq!(into_level_order_iter.next(), Some(4));
2093 /// assert_eq!(into_level_order_iter.next(), Some(2));
2094 /// assert_eq!(into_level_order_iter.next(), Some(5));
2095 /// assert_eq!(into_level_order_iter.next(), None);
2096 ///
2097 /// // bst.insert(10); -> COMPILE ERROR
2098 /// ```
2099 fn into_level_order_iter(self) -> IntoIter<T> {
2100 let mut elements = Vec::new();
2101 Node::recursive_consume_level_order_vec(self.root, &mut elements);
2102 elements.into_iter()
2103 }
2104}