Struct IterativeBST

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

Iterative Binary Search Tree implementation.

Important

This should be preferred over RecursiveBST for reasons listed in crate level documentation.

Implementations

impl<T: Ord> IterativeBST<T>

pub fn new() -> IterativeBST<T>

Creates an empty IterativeBST<T>

No nodes are allocated on the heap yet

Examples

use bst_rs::{BinarySearchTree, IterativeBST};

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

Trait Implementations

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

fn size(&self) -> usize

Returns the total number of nodes within the tree.

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst: IterativeBST<i32> = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::retrieve()) or None if element does not exist.

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::in_order_vec() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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, IterativeBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = IterativeBST::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 IterativeBST::asc_order_vec() as the underlying behaviour is exactly the same.

Example

use bst_rs::{BinarySearchTree, IterativeBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = IterativeBST::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, IterativeBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = IterativeBST::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, IterativeBST};

// Given a tree that looks like:
 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7
let mut bst = IterativeBST::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 IterativeBST::asc_order_vec().

Important

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

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::pre_order_vec().

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::in_order_vec().

Important

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

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::post_order_vec().

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::level_order_vec().

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::asc_order_iter() AND consumes the tree.

Important

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

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::pre_order_iter() AND consumes the tree.

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::in_order_iter() AND consumes the tree.

Important

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

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::post_order_iter() AND consumes the tree.

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST::level_order_iter() AND consumes the tree.

Example

use bst_rs::{BinarySearchTree, IterativeBST};

let mut bst = IterativeBST::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 IterativeBST<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 IterativeBST<T>

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

Formats the value using the given formatter.

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

fn default() -> IterativeBST<T>

Creates an empty IterativeBST<T>

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

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

Formats the value using the given formatter.

impl<T: Ord> Extend<T> for IterativeBST<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 IterativeBST<T>

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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

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

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

Creates a value from an iterator.

impl<T: Ord> PartialEq for IterativeBST<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.