Binary tree in Rust with O(1) memory destructor.

binary_tree.rs

#[repr(usize)]
pub enum Tree<T> {
    Leaf(T),
    Node(DropBox<Self>, DropBox<Self>),
}

impl<T> BoxDrop for Tree<T> {
    fn drop(self: Box<Self>) {
        #[repr(usize)]
        enum RawTree<T> {
            #[allow(dead_code)]
            Leaf(T),
            #[allow(dead_code)]
            Node(*mut Self, *mut Self),
            Link(*mut Self),
        }

        impl<T> RawTree<T> {
            unsafe fn leaf(mut this: *mut Self) -> *mut Self {
                loop {
                    this = match *this {
                        Self::Leaf(_) => break this,
                        Self::Node(l, _) => l,
                        Self::Link(l) => l,
                    };
                }
            }
        }

        unsafe {
            let mut this = Box::into_raw(self).cast();
            let mut leaf = RawTree::<T>::leaf(this);

            loop {
                this = match *Box::from_raw(this) {
                    RawTree::Leaf(_) => break,
                    RawTree::Node(l, r) => {
                        *leaf = RawTree::Link(r);
                        leaf = RawTree::leaf(r);
                        l
                    }
                    RawTree::Link(l) => l,
                };
            }
        }
    }
}