Binary search tree delete a node not working

Hey folks,

I am trying to implement the delete functionality for a binary search tree in Rust. However, the function doesn't seem to work as expected. Specifically, when I attempt to delete a node with no children, it doesn't get removed from the tree as it should.

Could you please help me figure out what might be going wrong?

Here is my code:

use std::cell::RefCell;
use std::rc::Rc;

pub type Link<'a, T> = Option<Rc<RefCell<Node<'a, T>>>>;

/// Binary search tree node
#[derive(Debug)]
pub struct Node<'a, T> {
    pub data: &'a T,
    pub left: Link<'a, T>,
    pub right: Link<'a, T>,
}

/// Binary search tree
#[derive(Debug)]
pub struct Tree<'a, T> {
    pub root: Link<'a, T>,
}

impl<'a, T: PartialOrd> Tree<'a, T> {
    pub fn min(&self) -> Option<&'a T> {
        let mut cur = self.root.to_owned();
        while let Some(node) = cur {
            let node = node.borrow();
            cur = node.left.to_owned();
            if cur.is_none() {
                return Some(node.data);
            }
        }
        None
    }

    /// Delete a node
    /// For deleting a node, there are three cases:
    /// - No child: Break the parent link.
    /// - One child: Link the parent directly with the child.
    /// - Two children: Two solutions.
    ///     * Find the minimum in the right subtree, copy the value into
    ///     the targeted node, then delete the duplicate (minimum node)
    ///     from the right subtree.
    ///     * Find the maximum in the left subtree, copy the value into
    ///     the targeted node, then delete the duplicate (maximum node)
    ///     from the left subtree.
    pub fn delete(&mut self, data: T) -> bool {
        if self.root.is_some() {
            return Tree::delete_recursive(&mut self.root, &data);
        }
        false
    }

    fn delete_recursive(node: &mut Option<Rc<RefCell<Node<'a, T>>>>, data: &T) -> bool {
        if node.is_none() {
            return false;
        }

        let wnode = node.to_owned().unwrap();
        let mut bnode = wnode.borrow_mut();

        if data == bnode.data {
            match (&bnode.left, &bnode.right) {
                // No child case
                (None, None) => {
                    *node = None;
                }
                // One child case
                (None, Some(_)) => {
                    *node = bnode.right.to_owned();
                }
                // One child case
                (Some(_), None) => {
                    *node = bnode.left.to_owned();
                }
                // Two children case
                (Some(_), Some(_)) => {
                    let min = Tree::min(&Tree::from(bnode.right.to_owned())).unwrap();
                    bnode.data = min;
                    Tree::delete_recursive(&mut bnode.right, min);
                }
            }
            true
        } else if data < bnode.data {
            Tree::delete_recursive(&mut bnode.left.to_owned(), data)
        } else if data > bnode.data {
            Tree::delete_recursive(&mut bnode.right.to_owned(), data)
        } else {
            false
        }
    }
}

Thanks for any help.

        } else if data < bnode.data {
            Tree::delete_recursive(&mut bnode.left.to_owned(), data)
        } else if data > bnode.data {
            Tree::delete_recursive(&mut bnode.right.to_owned(), data)
        } else {

In slower motion, this is...

let tmp: Option<_> = bnode.left.to_owned();
Tree::delete_recursive(&mut tmp);

...but you want to modify the Option stored inside bnode, not a temporary. Removed the to_owned.

        } else if data < bnode.data {
            Tree::delete_recursive(&mut bnode.left, data)
        } else if data > bnode.data {
            Tree::delete_recursive(&mut bnode.right, data)
        } else {

(I didn't test much else.)

3 Likes

By removing .to_owned(), it's working now. Thanks.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.