Struct RecursiveBST

pub struct RecursiveBST<T: Ord> { /* private fields */ }

Recursive Binary Search Tree implementation.

Important

It is also important to note that RecursiveBST is more likely to blow the stack and is generally less performant compared to IterativeBST.

For more information on why that is the case, please have a look at The Story of Tail Call Optimizations in Rust.

Implementations

impl<T: Ord> RecursiveBST<T>

pub fn new() -> RecursiveBST<T>

Creates an empty RecursiveBST<T>

No nodes are allocated on the heap yet

Examples

use bst_rs::{BinarySearchTree, RecursiveBST};

// Empty tree is created
let mut bst: RecursiveBST<i32> = RecursiveBST::new();
assert!(bst.is_empty())

Trait Implementations

impl<T: Ord> BinarySearchTree<T> for RecursiveBST<T>

fn size(&self) -> usize

Returns the total number of nodes within the tree.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(5);
bst.insert(10);
bst.insert(3);

assert_eq!(bst.size(), 3);

fn is_empty(&self) -> bool

Returns true if the binary search tree contains no nodes.

Examples

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst: RecursiveBST<i32> = RecursiveBST::new();
assert!(bst.is_empty());

fn is_not_empty(&self) -> bool

Returns true if the binary search tree contains one or more nodes.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
assert!(bst.is_empty());

bst.insert(2);

assert!(bst.is_not_empty());

fn insert(&mut self, value: T)

Inserts given value as a node.

Duplicate values are not allowed.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();

bst.insert(10);
bst.insert(10);   // Element is not inserted
bst.insert(5);
bst.insert(2);
bst.insert(15);
bst.insert(25);

assert_eq!(bst.size(), 5);

fn contains(&self, value: &T) -> bool

Returns true if the binary search tree contains an element with the given value.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(5);
bst.insert(2);
bst.insert(7);

assert!(bst.contains(&5));
assert!(!bst.contains(&10));

fn remove(&mut self, value: &T)

Removes the given value.

Tree will not be modified if trying to remove element that does not exist.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(5);
bst.insert(2);
bst.insert(7);
assert_eq!(bst.size(), 3);

bst.remove(&5);
bst.remove(&10); // Element is not removed
assert_eq!(bst.size(), 2);

fn retrieve(&self, value: &T) -> Option<&T>

Returns a reference to the element or None if element does not exist.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(5);
bst.insert(2);
bst.insert(7);

assert_eq!(bst.retrieve(&5), Some(&5));
assert_eq!(bst.retrieve(&10), None);

fn retrieve_as_mut(&mut self, value: &T) -> Option<&mut T>

Returns a mutable reference to the element (see RecursiveBST::retrieve()) or None if element does not exist.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(10);
bst.insert(5);

let optional_retrieved_value_as_mut = bst.retrieve_as_mut(&5);
assert_eq!(optional_retrieved_value_as_mut, Some(&mut 5));

let mut retrieved_value = optional_retrieved_value_as_mut.unwrap();
*retrieved_value = 2; // Change value inside tree to '2'

assert_eq!(bst.retrieve_as_mut(&5), None); // 5 does not exist anymore
assert_eq!(bst.retrieve_as_mut(&2), Some(&mut 2));

fn height(&self) -> Option<isize>

Returns the height or None if tree is empty.

The height is the number of edges between the root and it’s furthest leaf node.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = RecursiveBST::new();
assert_eq!(bst.height(), None);

bst.insert(4);
bst.insert(6);
bst.insert(2);
bst.insert(7);
bst.insert(5);
bst.insert(3);
bst.insert(1);

// The height is 2.
assert_eq!(bst.height(), Some(2));

fn min(&self) -> Option<&T>

Returns a reference to the minimum element of the tree or None if tree is empty.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
assert_eq!(bst.min(), None);

bst.insert(5);
bst.insert(2);
bst.insert(10);

assert_eq!(bst.min(), Some(&2));

fn max(&self) -> Option<&T>

Returns a reference to the maximum element of the tree or None if tree is empty.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
assert_eq!(bst.max(), None);

bst.insert(5);
bst.insert(2);
bst.insert(10);

assert_eq!(bst.max(), Some(&10));

fn remove_min(&mut self) -> Option<T>

Removes and returns the minimum element from the tree or None if tree is empty.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
assert_eq!(bst.remove_min(), None);

bst.insert(2);
bst.insert(5);
bst.insert(10);

assert_eq!(bst.size(), 3);
assert_eq!(bst.remove_min(), Some(2));
assert_eq!(bst.size(), 2);

fn remove_max(&mut self) -> Option<T>

Removes and returns the maximum element from the tree or None if tree is empty.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
assert_eq!(bst.remove_max(), None);

bst.insert(2);
bst.insert(5);
bst.insert(10);

assert_eq!(bst.size(), 3);
assert_eq!(bst.remove_max(), Some(10));
assert_eq!(bst.size(), 2);

fn asc_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in ascending order.

Important

This is function is analogous to RecursiveBST::in_order_vec() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(4);
bst.insert(6);
bst.insert(2);
bst.insert(7);
bst.insert(5);
bst.insert(3);
bst.insert(1);

assert_eq!(bst.asc_order_vec(), vec![&1, &2, &3, &4, &5, &6, &7]);

fn pre_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of a pre-order traversal.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = RecursiveBST::new();
bst.insert(4);
bst.insert(6);
bst.insert(2);
bst.insert(7);
bst.insert(5);
bst.insert(3);
bst.insert(1);

// The pre_order_vec is: [&4, &2, &1, &3, &6, &5, &7]
assert_eq!(bst.pre_order_vec(), vec![&4, &2, &1, &3, &6, &5, &7]);

fn in_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of an in-order traversal.

Important

This is function is analogous to RecursiveBST::asc_order_vec() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = RecursiveBST::new();
bst.insert(4);
bst.insert(6);
bst.insert(2);
bst.insert(7);
bst.insert(5);
bst.insert(3);
bst.insert(1);

// The in_order_vec is: [&1, &2, &3, &4, &5, &6, &7]
assert_eq!(bst.in_order_vec(), vec![&1, &2, &3, &4, &5, &6, &7]);

fn post_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of a post-order traversal.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = RecursiveBST::new();
bst.insert(4);
bst.insert(6);
bst.insert(2);
bst.insert(7);
bst.insert(5);
bst.insert(3);
bst.insert(1);

// The post_order_vec is: [&1, &3, &2, &5, &7, &6, &4]
assert_eq!(bst.post_order_vec(), vec![&1, &3, &2, &5, &7, &6, &4]);

fn level_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of a level-order traversal.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = RecursiveBST::new();
bst.insert(4);
bst.insert(6);
bst.insert(2);
bst.insert(7);
bst.insert(5);
bst.insert(3);
bst.insert(1);

// The level_order_vec is: [&4, &2, &6, &1, &3, &5, &7]
assert_eq!(bst.level_order_vec(), vec![&4, &2, &6, &1, &3, &5, &7]);

fn asc_order_iter(&self) -> IntoIter<&T>

Returns an iterator over RecursiveBST::asc_order_vec().

Important

This is function is analogous to RecursiveBST::in_order_iter() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut asc_order_iter = bst.asc_order_iter();

assert_eq!(asc_order_iter.next(), Some(&1));
assert_eq!(asc_order_iter.next(), Some(&2));
assert_eq!(asc_order_iter.next(), Some(&3));
assert_eq!(asc_order_iter.next(), Some(&4));
assert_eq!(asc_order_iter.next(), Some(&5));
assert_eq!(asc_order_iter.next(), None);

fn pre_order_iter(&self) -> IntoIter<&T>

Returns an iterator over RecursiveBST::pre_order_vec().

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut pre_order_iter = bst.pre_order_iter();

assert_eq!(pre_order_iter.next(), Some(&3));
assert_eq!(pre_order_iter.next(), Some(&1));
assert_eq!(pre_order_iter.next(), Some(&2));
assert_eq!(pre_order_iter.next(), Some(&4));
assert_eq!(pre_order_iter.next(), Some(&5));
assert_eq!(pre_order_iter.next(), None);

fn in_order_iter(&self) -> IntoIter<&T>

Returns an iterator over RecursiveBST::in_order_vec().

Important

This is function is analogous to RecursiveBST::asc_order_iter() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut in_order_iter = bst.in_order_iter();

assert_eq!(in_order_iter.next(), Some(&1));
assert_eq!(in_order_iter.next(), Some(&2));
assert_eq!(in_order_iter.next(), Some(&3));
assert_eq!(in_order_iter.next(), Some(&4));
assert_eq!(in_order_iter.next(), Some(&5));
assert_eq!(in_order_iter.next(), None);

fn post_order_iter(&self) -> IntoIter<&T>

Returns an iterator over RecursiveBST::post_order_vec().

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut post_order_iter = bst.post_order_iter();

assert_eq!(post_order_iter.next(), Some(&2));
assert_eq!(post_order_iter.next(), Some(&1));
assert_eq!(post_order_iter.next(), Some(&5));
assert_eq!(post_order_iter.next(), Some(&4));
assert_eq!(post_order_iter.next(), Some(&3));
assert_eq!(post_order_iter.next(), None);

fn level_order_iter(&self) -> IntoIter<&T>

Returns an iterator over RecursiveBST::level_order_vec().

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut level_order_iter = bst.level_order_iter();

assert_eq!(level_order_iter.next(), Some(&3));
assert_eq!(level_order_iter.next(), Some(&1));
assert_eq!(level_order_iter.next(), Some(&4));
assert_eq!(level_order_iter.next(), Some(&2));
assert_eq!(level_order_iter.next(), Some(&5));
assert_eq!(level_order_iter.next(), None);

fn into_asc_order_iter(self) -> IntoIter<T>

Returns RecursiveBST::asc_order_iter() AND consumes the tree.

Important

This is function is analogous to RecursiveBST::into_in_order_iter() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut into_asc_order_iter = bst.into_asc_order_iter();

assert_eq!(into_asc_order_iter.next(), Some(1));
assert_eq!(into_asc_order_iter.next(), Some(2));
assert_eq!(into_asc_order_iter.next(), Some(3));
assert_eq!(into_asc_order_iter.next(), Some(4));
assert_eq!(into_asc_order_iter.next(), Some(5));
assert_eq!(into_asc_order_iter.next(), None);

// bst.insert(10); -> COMPILE ERROR

fn into_pre_order_iter(self) -> IntoIter<T>

Returns RecursiveBST::pre_order_iter() AND consumes the tree.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut into_pre_order_iter = bst.into_pre_order_iter();

assert_eq!(into_pre_order_iter.next(), Some(3));
assert_eq!(into_pre_order_iter.next(), Some(1));
assert_eq!(into_pre_order_iter.next(), Some(2));
assert_eq!(into_pre_order_iter.next(), Some(4));
assert_eq!(into_pre_order_iter.next(), Some(5));
assert_eq!(into_pre_order_iter.next(), None);

// bst.insert(10); -> COMPILE ERROR

fn into_in_order_iter(self) -> IntoIter<T>

Returns RecursiveBST::in_order_iter() AND consumes the tree.

Important

This is function is analogous to RecursiveBST::asc_order_iter() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut into_in_order_iter = bst.into_in_order_iter();

assert_eq!(into_in_order_iter.next(), Some(1));
assert_eq!(into_in_order_iter.next(), Some(2));
assert_eq!(into_in_order_iter.next(), Some(3));
assert_eq!(into_in_order_iter.next(), Some(4));
assert_eq!(into_in_order_iter.next(), Some(5));
assert_eq!(into_in_order_iter.next(), None);

// bst.insert(10); -> COMPILE ERROR

fn into_post_order_iter(self) -> IntoIter<T>

Returns RecursiveBST::post_order_iter() AND consumes the tree.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut into_post_order_iter = bst.into_post_order_iter();

assert_eq!(into_post_order_iter.next(), Some(2));
assert_eq!(into_post_order_iter.next(), Some(1));
assert_eq!(into_post_order_iter.next(), Some(5));
assert_eq!(into_post_order_iter.next(), Some(4));
assert_eq!(into_post_order_iter.next(), Some(3));
assert_eq!(into_post_order_iter.next(), None);

// bst.insert(10); -> COMPILE ERROR

fn into_level_order_iter(self) -> IntoIter<T>

Returns RecursiveBST::level_order_iter() AND consumes the tree.

Example

use bst_rs::{BinarySearchTree, RecursiveBST};

let mut bst = RecursiveBST::new();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(1);
bst.insert(2);

let mut into_level_order_iter = bst.into_level_order_iter();

assert_eq!(into_level_order_iter.next(), Some(3));
assert_eq!(into_level_order_iter.next(), Some(1));
assert_eq!(into_level_order_iter.next(), Some(4));
assert_eq!(into_level_order_iter.next(), Some(2));
assert_eq!(into_level_order_iter.next(), Some(5));
assert_eq!(into_level_order_iter.next(), None);

// bst.insert(10); -> COMPILE ERROR

impl<T: Ord + Clone> Clone for RecursiveBST<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Ord> Debug for RecursiveBST<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord> Default for RecursiveBST<T>

fn default() -> RecursiveBST<T>

Creates an empty RecursiveBST<T>

impl<T: Ord + Debug> Display for RecursiveBST<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord> Extend<T> for RecursiveBST<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Ord + Clone> From<&[T]> for RecursiveBST<T>

fn from(slice: &[T]) -> Self

Converts to this type from the input type.

impl<T: Ord> From<Vec<T>> for RecursiveBST<T>

fn from(vec: Vec<T>) -> Self

Converts to this type from the input type.

impl<T: Ord> FromIterator<T> for RecursiveBST<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: Ord> PartialEq for RecursiveBST<T>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.