Struct ds_bst::BinarySearchTree

pub struct BinarySearchTree<T> { /* fields omitted */ }

Implements a Binary Search Tree. This is a recursive data structure and left and right refers to sub trees.

Tree is an entry point for the root node. It’s much simpler to create a tree form a vector.

Example

Implements binary search tree with traversal (inorder)

use ds_bst::BinarySearchTree;

let mut root = BinarySearchTree::from(vec![1,2,3,4,5,6,7,8,9]);
root.insert(10);
let ordered: Vec<_> = root.inorder();

let mut root2 = BinarySearchTree::new(5);
root2.insert(1);
root2.insert(6);

Implementations

impl<T: PartialOrd + Copy> BinarySearchTree<T>

pub fn new(v: T) -> BinarySearchTree<T>

Contructor creates BinarySearchTree from one element

pub fn from(data: Vec<T>) -> BinarySearchTree<T>

Delegates tree building to BinarySearchTree::build_recursive() This sorts vector input and pass splice to tree builder.

pub fn build_recursive(
    data: &[T],
    start: isize,
    end: isize
) -> Option<Box<BinarySearchTree<T>>>

Recursively builds tree maintaining BST properties. Uses O(n) time.

pub fn inorder(&self) -> Vec<T>

Inorder traverse tree which yields elements in sorted order. Uses O(n) time. TODO: Implement Iterator

pub fn preorder(&self) -> Vec<T>

Traverse tree in preorder. Uses O(n) time. TODO: Implement using iterator

pub fn insert(&mut self, val: T)

Inserts an element in a tree. Uses O(n) time.

pub fn exists(&self, val: T) -> bool

Checks if element exists in a tree. Uses O(n) time.

pub fn find_min(&self) -> T

Finds minimum element in a tree. Uses O(n) time.

pub fn find_max(&self) -> T

Finds maximum element in a tree. Uses O(n) time.