JoelKit

Algorithms

Sorting

Insertion Sort

In Place

Python

# from joelkit.algorithms import insertion_sort

def insertion_sort(arr): #in place
    for i in range(1, len(arr)): #first item already sorted
        to_move = arr[i]
        curr_i = i
        while curr_i > 0 and arr[curr_i - 1] > to_move:
            arr[curr_i] = arr[curr_i - 1] #nudge item to the right
            curr_i -= 1
        arr[curr_i] = to_move

C++

template <typename T>
void insertion_sort(std::vector<T>& v) {
    for (int i = 1; i < v.size(); i++) {
        T el = v[i]; //element to insert
        int curr_i = i;
        while (curr_i > 0 && v[curr_i - 1] > el) {
            v[curr_i] = v[curr_i - 1];
            curr_i--;
        }
        v[curr_i] = el;
    }
}

Runtime

Best case: O(n)

Worst case: O(n²)

Quick Sort

In Place

Python

# from joelkit.algorithms import quick_sort

def quick_sorted(lst): #-> sorted list
    # Base case: if list is empty or size 1, nothing to be done
    if len(lst) <= 1:
        return lst
    
    # Recursive case: find a pivot (efficiently), then partition the list so the items to the left of the partition are less than the partition and the items to the right of the partition are greater than the partition
    pivot_i = find_pivot_index(0, len(lst))
    pivot = lst[pivot_i]

    left = []
    right = []
    for current_index, current_value in enumerate(lst):
        if current_index == pivot_i:
            continue
        if current_value <= pivot:
            left.append(current_value)
        else:
            right.append(current_value)
    
    sorted_left = quick_sorted(left)
    sorted_right = quick_sorted(right)

    return [*sorted_left, pivot, *sorted_right]


def find_pivot_index(start_i, end_i):
    # Naive deterministic implementation would be
    # return start_i

    if start_i == end_i:
        return start_i
    
    return random.randint(start_i, end_i - 1) #exclude end_i as a possibility

C++

template <typename T>
std::vector<T> quick_sorted(const std::vector<T>& lst) {
    // Base case
    if (lst.size() <= 1)
        return lst;

    // Recursive case
    int pivot_i = find_pivot_index(0, lst.size());
    T pivot = lst[pivot_i];

    std::vector<T> left;
    std::vector<T> right;
    for (int curr_i = 0; curr_i < lst.size(); curr_i++) {
        if (curr_i == pivot_i) {
            continue;
        }
        T curr_val = lst[curr_i];
        if (curr_val <= pivot) {
            left.push_back(curr_val);
        } else {
            right.push_back(curr_val);
        }
    }

    std::vector<T> sorted_left = quick_sorted(left);
    std::vector<T> sorted_right = quick_sorted(right);
    
    std::vector<T> out = sorted_left;
    out.push_back(pivot);
    out.insert(out.end(), sorted_right.begin(), sorted_right.end());
    return out;
}

int find_pivot_index(int start_i, int end_i) {
    if (start_i == end_i)
        return start_i;

    return start_i + rand() % (end_i - start_i);
}

Runtime

Expected: O(nlogn)

Worst case: O(n²)

Merge Sort

In Place

Python

# from joelkit.algorithms import merge_sort

def merge_sorted(l):
    # Base case: already sorted
    if len(l) == 0 or len(l) == 1:
        return l
    
    # Recursive step
    middle = len(l) // 2
    left = l[0:middle]
    right = l[middle:]
    left_sorted = merge_sorted(left)
    right_sorted = merge_sorted(right)
    return merge(left_sorted, right_sorted)


def merge(l1, l2):
    merged = [] #out
    i1 = 0 #index on l1
    i2 = 0
    while i1 < len(l1) or i2 < len(l2): #while there are still items to process
        if i1 == len(l1): #must process l2 because l1 already all processed
            merged.append(l2[i2])
            i2 += 1
        elif i2 == len(l2):
            merged.append(l1[i1])
            i1 += 1
        else: #add that which is smaller
            if l1[i1] <= l2[i2]:
                merged.append(l1[i1])
                i1 += 1
            else:
                merged.append(l2[i2])
                i2 += 1

    return merged

C++

template <typename T>
std::vector<T> merge_sorted(const std::vector<T>& l) {
    if (l.size() == 0 || l.size() == 1)
        return l;
    
    int middle = l.size() / 2;
    std::vector<T> left(l.begin(), l.begin() + middle);
    std::vector<T> right(l.begin() + middle, l.end());
    std::vector<T> left_sorted = merge_sorted(left);
    std::vector<T> right_sorted = merge_sorted(right);
    return merge(left_sorted, right_sorted);
}

template <typename T>
std::vector<T> merge(const std::vector<T>& l1, const std::vector<T>& l2) {
    std::vector<T> merged(l1.size() + l2.size());
    auto merged_it = merged.begin();

    auto i1 = l1.begin();
    auto i2 = l2.begin();
    while (i1 != l1.end() || i2 != l2.end()) { //while there is still something to process
        if (i1 == l1.end()) { //must do l2
            *merged_it = *i2;
            merged_it++;
            i2++;
        } else if (i2 == l2.end()) { //must do l1
            *merged_it = *i1;
            merged_it++;
            i1++;
        } else {
            if (*i1 < *i2) {
                *merged_it = *i1;
                i1++;
                merged_it++;
            } else {
                *merged_it = *i2;
                i2++;
                merged_it++;
            }
        }
    }
    return merged;
}

Runtime

O(nlogn)

Bubble Sort

Python

# from joelkit.algorithms import bubble_sort

d# Elements bubble their way to the right
# Topmost element bubbles to the last element
# Second-largest element bubbles to the second to last element
# ...
def bubble_sort(arr):
    for i in range(len(arr) - 1): #need -1 because j+1
        for j in range(0, len(arr) - 1 - i): #don't need to consider last i items because they are sorted (i largest items bubbled up)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

C++

template <typename T>
void bubble_sort(std::vector<T>& l) {
    for (int i = 0; i < l.size() - 1; i++) {
        for (int j = 0; j < l.size() - 1 - i; j++) {
            if (l[j] > l[j + 1]) {
                T temp = l[j];
                l[j] = l[j + 1];
                l[j + 1] = temp;
            }
        }
    }
}

Runtime

O(n²)

Other

# from joelkit.algorithms import k_select

def find_pivot(lst):
    medians = []
    for i in range(0, len(lst), 5):
        five = []
        for j in range(i, i + 5):
            if j >= len(lst):
                break
            five.append((j, lst[j]))
        five.sort(key=lambda x : x[1])
        median = five[len(five) // 2]
        medians.append(median)
    return sorted(medians, key=lambda x : x[1])[len(medians) // 2]
    # return k_select(medians, len(medians) // 2)


def k_select(lst, k):
    if k > len(lst) or len(lst) == 0: #not possible (check)
        return None
    if len(lst) < 10:
        return sorted(lst)[k]
    
    pivot_index, pivot_value = find_pivot(lst)
    
    # Partition
    left = []
    right = []
    for i, item in enumerate(lst):
        if i == pivot_index:
            continue
        if item <= pivot_value:
            left.append(item)
        else:
            right.append(item)
    
    # Recursion
    if k == len(left): #is the pivot
        return pivot_value
    if k < len(left):
        return k_select(left, k)
    else:
        return k_select(right, k - len(left) - 1)

template <typename T>
using IndexAndValue = std::pair<int, T>;

/** Finds median of medians. @returns its index in the passed-in list as well as its value */
template <typename T, typename KeyFunc>
IndexAndValue<T> find_pivot(std::vector<T> list, KeyFunc key) {
    std::vector<IndexAndValue<T>> medians;
    for (int i = 0; i < list.size(); i += 5) {
        std::vector<IndexAndValue<T>> five;
        for (int j = i; j < list.size() && j < i + 5; j++) {
            five.push_back(
                std::make_pair(j, list[j])
            );
        }
        insertion_sort(five, [&key](IndexAndValue<T> item) { return key(item.second); }); //insertion sort is nice on small lists
        IndexAndValue<T> median = five[five.size() / 2]; //do this instead of [2] in the case that |five|<5
        medians.push_back(median);
    }
    insertion_sort(medians, [](IndexAndValue<T> item) { return item.second; });
    IndexAndValue<T> median_of_medians = medians[medians.size() / 2];
    // IndexAndValue<T> median_of_medians = k_select(medians, medians.size() / 2, [&key](IndexAndValue<T> el) {
    //     return key(el.second);
    // });
    return median_of_medians;
}

template <typename T, typename KeyFunc>
T k_select(std::vector<T> list, int k, KeyFunc key) {
    if (list.size() < 50) //base case
        return insertion_sorted(list, key)[k];
    
    
    IndexAndValue<T> pivot = find_pivot(list, key);

    // Partition
    std::vector<T> left;
    std::vector<T> right;
    for (int i = 0; i < list.size(); i++) {
        T item = list[i];
        if (i == pivot.first) //skip the pivot. It is neither in left nor right
            continue;
        if (key(item) <= key(pivot.second))
            left.push_back(item);
        else
            right.push_back(item);
    }
    
    // Recursive step
    if (k == left.size()) //is pivot
        return pivot.second;
    else if (k < left.size())
        return k_select(left, k, key);
    else
        return k_select(right, k - left.size() - 1, key); //takes out the left and the pivot
}

template <typename T>
T k_select(std::vector<T> list, int k) {
    return k_select(list, k, [](T el) { return el; }); //use the self selector
}

# from joelkit.algorithms import partition

def partition(lst, start_i, end_i, pivot_i): # returns new position of the pivot
    p = lst[pivot_i] #pivot value

    # 1. Put the pivot at the beginning
    lst[start_i], lst[pivot_i] = lst[pivot_i], lst[start_i]

    # 2. Incorporate every vertex v into the left or right
    # Everything before l_i (left index) belongs to the left (<p)
    # Everything after l_i but before r_i belongs to the right (>p)
    # l_i points to the first element in the right, called r^
    # r_i points to v, the current value under consideration
    l_i = start_i + 1
    for r_i in range(start_i + 1, end_i): 
        v = lst[r_i] #decide if v should be in left or right
        if v > p: #v should be in the right
            continue
        if v <= p: #v should be in the left
            lst[l_i], lst[r_i] = lst[r_i], lst[l_i] #l_i points to r^
            l_i += 1

    # 3. Move pivot to end of the left
    lst[start_i], lst[l_i - 1] = lst[l_i - 1], lst[start_i]
    return l_i - 1 #l_i - 1 is where the pivot is now

#include "partition.h"

template <typename T>
int partition(std::vector<T>& lst, int start_i, int end_i, int pivot_i) {
    T p = lst[pivot_i];

    // 1. Put pivot at beginning
    lst[pivot_i] = lst[start_i];
    lst[start_i] = p;

    // 2.
    int l_i = start_i + 1;
    for (int r_i = start_i + 1; r_i < end_i; r_i++) {
        T v = lst[r_i];
        if (v > p) {
            continue;
        }
        if (v <= p) {
            T rhat = lst[l_i];
            lst[l_i] = lst[r_i];
            lst[r_i] = rhat;
            l_i++;
        }
    }
    // 3. Move pivot to end of the left
    lst[start_i] = lst[l_i - 1];
    lst[l_i - 1] = p;
    return l_i - 1;
}

Data Structures

Stack

Stack supports push, pop, and peek. It's a last in first out (LIFO) data structure.

C++

Header File

#include <cstddef>
#include <iostream>

template <typename T>
class Stack {
private:
    T* elems_;
    size_t size_ = 0;
    size_t capacity_ = 100;

    /**
     * when capacity is exceeded, double capacity
     */
    void grow();

public:
    Stack();
    Stack(size_t capacity);
    ~Stack();

    void push(T el);
    T pop();
    T peek() const;
    
    size_t size() const;
    bool is_empty() const;

    template <typename U>
    friend std::ostream& operator<<(std::ostream& os, const Stack<U>& s);
};

Implementation File

template <typename T>
Stack<T>::Stack() {
    elems_ = new T[capacity_];
}

template <typename T>
Stack<T>::Stack(size_t capacity) {
    capacity_ = capacity;
    elems_ = new T[capacity];
}

template <typename T>
Stack<T>::~Stack() {
    delete[] elems_;
}

template <typename T>
void Stack<T>::push(T elem) {
    if (capacity_ == size_) {
        grow();
    }
    elems_[size_] = elem;
    size_++;
}

template <typename T>
T Stack<T>::pop() {
    T elem = elems_[size_ - 1];
    size_--;
    return elem;
}

template <typename T>
T Stack<T>::peek() const {
    return elems_[size_ - 1];
}

template <typename T>
size_t Stack<T>::size() const {
    return size_;
}

template <typename T>
bool Stack<T>::is_empty() const {
    return size_ == 0;
}

template <typename T>
void Stack<T>::grow() {
    size_t new_capacity_ = capacity_ * 2;
    T* new_elems_ = new T[new_capacity_];

    // Insert the old elements
    for (int i = 0; i < capacity_; i++) {
        new_elems_[i] = elems_[i];
    }
    
    delete[] elems_;
    elems_ = new_elems_;
    capacity_ = new_capacity_;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const Stack<T>& s) {
    for (int i = 0; i < s.size_; i++) {
        std::cout << s.elems_[i] << " ";
    }
    return os;
}

Queue

Queue supports enqueue, dequeue, and peek. It's a first in first out (FIFO) data structure.

C++

Header File

template <typename T>
class Queue {
private:
    T* elems_;
    int h_ = 0; //index of head
    int t_ = 0; //index of tail
    size_t capacity_ = 100;

    void grow();
    
public:
    Queue();
    ~Queue();

    std::size_t size() const;
    bool is_empty() const;

    void enqueue(T new_element);
    T dequeue();
    T peek() const;

    template <typename U>
    friend std::ostream& operator<<(std::ostream& os, const Queue<U>& q);
};

Implementation File

#include "queue.h"

template <typename T>
Queue<T>::Queue() {
    elems_ = new T[capacity_];
}

template <typename T>
Queue<T>::~Queue() {
    delete[] elems_;
}

template <typename T>
std::size_t Queue<T>::size() const {
    int out = t_ - h_;
    if (out < 0)
        out += capacity_;
    return out;
}

template <typename T>
bool Queue<T>::is_empty() const {
    return size() == 0;
}

template <typename T>
void Queue<T>::enqueue(T elem) {
    elems_[t_] = elem;
    t_++;
    if (t_ == capacity_)
        t_ = 0;
    
    if (t_ == h_)
        grow(); //grow size by 2-fold
}

template <typename T>
T Queue<T>::dequeue() {
    T out = elems_[h_];
    h_++;
    if (h_ == capacity_)
        h_ = 0;
    return out;
}

template <typename T>
T Queue<T>::peek() const {
    T out = elems_[h_];
    return out;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const Queue<T>& q) {
    int p = q.h_;
    while (p != q.t_) {
        std::cout << q.elems_[p] << " ";

        p++;
        if (p == q.capacity_) //loop around
            p = 0;
    }
    return os;
}

template <typename T>
void Queue<T>::grow() { //called when h_ is the same as t_
    // std::cout << "Grow called" << std::endl;
    size_t new_capacity = capacity_ * 2;
    T* new_elems = new T[new_capacity];
    int new_elem_i = 0;

    int p = h_;
    bool first_round = true;
    while (!(p == t_ && first_round == false)) { //DeMorganed: p != t_ || first_round
        new_elems[new_elem_i] = elems_[p];
        new_elem_i++;
        
        p++;
        if (p == capacity_)
            p = 0;
        first_round = false;
    }
    
    delete[] elems_;
    elems_ = new_elems;
    capacity_ = new_capacity;

    h_ = 0;
    t_ = new_elem_i;
}

Linked List

This linked list implementation allows for O(1) insertion to the front and back.

C++

Header File

#pragma once

#include <iostream>

template <typename T>
class Node {
public:
    Node(T value);
    Node(T value, Node* next);

    T value;
    Node* next;
};

template <typename T>
class LinkedList {
public:
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;
    
    LinkedList();
    
    /** insert at front of list */
    void insert(T value);
    void insert_back(T value);
    void insert_at(size_t index, T value);
    
    Node<T>* operator[](size_t index);
    
    size_t size() const;

    template <typename U>
    friend std::ostream& operator<<(std::ostream& os, const LinkedList<U>& ll);
};

Implementation File

template <typename T>
Node<T>::Node(T value, Node<T>* next) {
    this->value = value;
    this->next = next;
}

template <typename T>
Node<T>::Node(T value) {
    this->value = value;
    this->next = nullptr;
}

template <typename T>
LinkedList<T>::LinkedList() {}

template <typename T>
void LinkedList<T>::insert(T value) {
    Node<T>* new_head = new Node(value);
    new_head->next = head;
    head = new_head;
    if (tail == nullptr)
        tail = new_head;
}

template <typename T>
void LinkedList<T>::insert_back(T value) {
    Node<T>* new_tail = new Node(value);
    tail->next = new_tail; //old tail now points to new tail
    tail = new_tail;
}

template <typename T>
void LinkedList<T>::insert_at(size_t index, T value) {
    Node<T>* n = new Node(value);
    
    Node<T>* before = head; //node right before where the new node will be
    for (int i = 0; i < index - 1; i++) {
        before = before->next;
    }
    n->next = before->next;
    before->next = n;
}

template <typename T>
Node<T>* LinkedList<T>::operator[](size_t index) {
    Node<T>* n = head;
    for (int i = 0; i < index; i++) {
        n = n->next;
    }
    return n;
}

template <typename T>
size_t LinkedList<T>::size() const {
    Node<T>* n = this->head;
    size_t out = 0;
    while (n != nullptr) {
        out++;
        n = n->next;
    }
    return out;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const LinkedList<T>& l) {
    Node<T>* n = l.head;
    while (n != nullptr) {
        os << n->value << " ";
        n = n->next;
    }
    return os;
}

BST

Binary search tree that supports insert, contains, and remove, each in O(logn) time when the tree is balanced.

C++

Header File

#include <iostream>
#include <utility> //std::tuple
#include <optional>

template <typename T>
struct BSTNode {
    T value;
    BSTNode<T>* left = nullptr;
    BSTNode<T>* right = nullptr;

    BSTNode(T value): value(value) {}
};

/** templates are helpful so you can make it a BST of any comparable object (int, float, double, Decimal, string) */
template <typename T>
class BST {
public:
    BSTNode<T>* root = nullptr;

    /** returns if an element was inserted */
    bool insert(T el);
    bool contains(T el) const;
    bool contains_rec(T el) const;
    /** @returns if an element was removed */
    bool remove(T el);

    template <typename U>
    friend std::ostream& operator<<(std::ostream& os, const BST<U>& bst);
private:
    void print_node(BSTNode<T>* n, int level = 0) const;
    bool contains_rec_helper(T el, BSTNode<T>* current_node) const;
    
    /**
     * This method is useful for remove
     * @returns optional<(parent, child, is_left)>; pointer to parent node, pointer to child node, boolean for if it is the left child (true is left, false is right). if the item is not found, returns None
     * */
    std::optional<std::tuple<BSTNode<T>*, BSTNode<T>*, bool>> find_node_and_its_parent(T el);
};

Implementation File

template <typename T>
bool BST<T>::insert(T el) {
    BSTNode<T>* new_node = new BSTNode<T>(el);

    if (root == nullptr) {
        root = new_node;
        return true;
    }

    BSTNode<T>* parent = root; //parent of the new node
    while (true) {
        if (el > parent->value) {
            if (parent->right == nullptr) {
                parent->right = new_node;
                return true;
            }
            parent = parent->right;
        } else if (el == parent->value) {
            return false;
        } else { // el < parent->value
            if (parent->left == nullptr) {
                parent->left = new_node;
                return true;
            }
            parent = parent->left;
        }
    }
}

template <typename T>
bool BST<T>::contains(T el) const { //iterative approach
    BSTNode<T>* current_node = root;
    while (current_node != nullptr) {
        if (el == current_node->value)
            return true;
        else if (el > current_node->value)
            current_node = current_node->right;
        else
            current_node = current_node->left;
    }
    return false;
}

template <typename T>
bool BST<T>::contains_rec(T el) const { //recursive implementation
    return contains_rec_helper(el, root);
}

template <typename T>
bool BST<T>::contains_rec_helper(T el, BSTNode<T>* current_node) const {
    if (current_node == nullptr)
        return false;
    if (current_node->value == el)
        return true;
    if (el > current_node->value) //it must be on the right if it is there
        return contains_rec_helper(el, current_node->right);
    else //el < current_node->value
        return contains_rec_helper(el, current_node->left);
}

template <typename T>
using ParentChildRel = std::tuple<BSTNode<T>*, BSTNode<T>*, bool>;

template <typename T>
std::optional<ParentChildRel<T>> BST<T>::find_node_and_its_parent(T el) {
    BSTNode<T>* parent = nullptr;
    BSTNode<T>* child = root;
    bool is_left = false;

    while (child != nullptr) {
        if (el == child->value) {
            return std::make_tuple(parent, child, is_left);
        } else if (el > child->value) { //go right
            parent = child;
            child = child->right;
            is_left = false;
        } else { //el < child->value, go left
            parent = child;
            child = child->left;
            is_left = true;
        }
    }
    
    return {};
}


template <typename T>
bool BST<T>::remove(T el) {
    std::optional<ParentChildRel<T>> res = find_node_and_its_parent(el);
    if (!res) //cannot remove it because it is not in the tree
        return false;
    
    ParentChildRel<T> unwrapped_res = res.value();
    BSTNode<T>* parent = std::get<0>(unwrapped_res); //parent of node to delete
    BSTNode<T>* child = std::get<1>(unwrapped_res); //node to delete
    bool is_left = std::get<2>(unwrapped_res);
    
    // Case 1: deleting a leaf
    if (child->left == nullptr && child->right == nullptr) {
        if (parent == nullptr) { //child is root node
            // In this case, deleting root node with nothing else in tree (root is leaf)
            root = nullptr;
            return true;
        }

        if (is_left) {
            parent->left = nullptr;
            return true;
        } else {
            parent->right = nullptr;
            return true;
        }
    }

    // Case 2: deleting root (that has children by not being a leaf)
    // Since it is the root, we have to update the root pointer (parent is nullptr)
    if (parent == nullptr) { //child is root
        if (child->right != nullptr) {
            BSTNode<T>* replacement = child->right;
            BSTNode<T>* parent_of_replacement = child;
            while (replacement->left != nullptr) {
                parent_of_replacement = replacement;
                replacement = replacement->left;
            }

            BSTNode<T>* old_replacement_right = replacement->right;
            replacement->left = child->left;
            replacement->right = child->right;
            root = replacement;
            
            delete child;

            parent_of_replacement->left = old_replacement_right;
            
            return true;
        }

        // In this case, since child cannot be a leaf, it only has a ->left
        BSTNode<T>* replacement = child->left;
        BSTNode<T>* parent_of_replacement = child;
        while (replacement->right != nullptr) {
            parent_of_replacement = replacement;
            replacement = replacement->right;
        }
        
        BSTNode<T>* old_replacement_left = replacement->left;
        replacement->left = child->left;
        root = replacement;
        // we already know replacement->right is null so it is fine

        delete child;

        parent_of_replacement->right = old_replacement_left;

        return true;
    }

    // Case 3: deleting a non-root interior node
    // Since it is an interior node, it has to have a child
    // Case 3a: deleted node has a right child
    if (child->right != nullptr) {
        BSTNode<T>* replacement = child->right;
        BSTNode<T>* parent_of_replacement = child;
        while (replacement->left != nullptr) {
            parent_of_replacement = replacement;
            replacement = replacement->left;
        }

        BSTNode<T>* old_replacement_right = replacement->right;
        replacement->left = child->left;
        if (child->right != replacement) {
            replacement->right = child->right;
        }

        if (is_left)
            parent->left = replacement;
        else
            parent->right = replacement;

        delete child;
        return true;
    }

    // Case 3b: deleted node only has a left child
    // implicitly, we know that child->left != nullptr since it is not a leaf and does not have a right node
    BSTNode<T>* replacement = child->left;
    BSTNode<T>* parent_of_replacement = child;

    while (replacement->right != nullptr) {
        parent_of_replacement = replacement;
        replacement = replacement->right;
    }

    BSTNode<T>* old_replacement_left = replacement->left;
    if (child->left != replacement) {
        replacement->left = child->left;
    }
    if (is_left)
        parent->left = replacement;
    else
        parent->right = replacement;
    parent_of_replacement->right = old_replacement_left;

    delete child;
    return true;
}

/** this printing method is nice because leave nodes are surrounded like so (3) */
template <typename T>
std::ostream& operator<<(std::ostream& os, const BST<T>& bst) {
    bst.print_node(bst.root, 0);
    return os;
}

template <typename T>
void BST<T>::print_node(BSTNode<T>* n, int level) const {
    if (n == nullptr) return;

    int paren_type = level % 4;
    char open_paren = '(';
    char close_paren = ')';
    if (paren_type == 1) {
        open_paren = '<';
        close_paren = '>';
    } else if (paren_type == 2) {
        open_paren = '{';
        close_paren = '}';
    } else if (paren_type == 3) {
        open_paren = '[';
        close_paren = ']';
    }
    
    if (n->left != nullptr) {
        std::cout << open_paren;
        print_node(n->left, level + 1);
        std::cout << close_paren << " ← ";
    }
    std::cout << n->value;
    if (n->right != nullptr) {
        std::cout << " → " << open_paren;
        print_node(n->right, level + 1);
        std::cout << close_paren;
    }
}