Search for Successor of BST node, "clone to satisfy borrow checker" disaster

Question

I am trying to implement a BST in Rust. My struct looks like this:

pub struct Node<T> {  
    key: T,  
    parent: Option<Box<Node<T>>>,  
    left: Option<Box<Node<T>>>,  
    right: Option<Box<Node<T>>>,  
}  

I am working on a method for finding the successor of a current node. After a prolonged fight with the borrow checker, I made it work, but it now looks like this:

//If right node exists - successor is a min node in it.
//Else - go up a parent node. If parent is None, no successor.
//If origin was parent's left node - parent is a successor.
//Else - go up another level.
pub fn succ(&self) -> Option<Box<Node<T>>> {

    match self.right {
        Some(ref node) => Some(node.min()),
        None => {
            let mut origin = Box::new(self.clone()); //To match types
            let mut parent = origin.parent.clone(); //`Node<T>` not a copy type

            loop {
                let parent_node = match parent.clone() {
                    Some(node) => node,
                    None => break,
                };
                let right_of_parent = match parent_node.clone().right {
                    Some(node) => node,
                    None => break,
                };
                if *origin != *right_of_parent {
                    break;
                }

                origin = parent_node;
                parent = origin.parent.clone();
            }
            parent
        }
    }
}  

If I remove all the .clone()s, the compiler starts crying with "partial moved value" and "cannot assign because borrowed" errors. Is there a way to make this code more idiomatic and less of a cloning hell?

UPD:
Wanted to post the solution I ended up with.
First of all, above code doesn't work, as the parent field contained not a reference, but a copy of a parent node. So in the end the question turned into "how to implement a reference to a parent node".
I considered the answer below, some books and relevant answers and in the end i came to conclusion that it don't worth it for a toy project that I didn't even plan to publish online. I've found not the most efficient, but definitely simpler solution - not to use parent reference at all.
I removed parent field from the structure above and created another structure:

pub struct Tree<T> {
    root: Option<Box<Node<T>>>,
}

And now I search for parent from the root of the tree. My succ function now looks like this:

fn succ<'a>(&'a self, node: &'a Node<T>) -> Option<&Node<T>> {
    match node.right {
        Some(ref rnode) => rnode.min(),
        None => {
            let mut succ = None;
            let mut root = self.root.as_ref();
            loop {
                root = match root {
                    Some(ref rootnode) => {
                        match node.key.cmp(&rootnode.key) {
                            Ordering::Less => {
                                succ = Some(&***rootnode);
                                rootnode.left.as_ref()
                            }
                            Ordering::Greater => rootnode.right.as_ref(),
                            Ordering::Equal => break,
                        }
                    }
                    None => break,
                }
            }
            succ
        }
    }
}

Answer 1

Welcome to Rust and Stack Overflow!

The main issue here is Node definition:

pub struct Node<T> {  
    key: T,  
    parent: Option<Box<Node<T>>>,  
    left: Option<Box<Node<T>>>,  
    right: Option<Box<Node<T>>>,  
}

In Rust, Box<T> owns the value rather than being a pointer which can alias. You wouldn't be a able to create any non-trivial trees.

Instead of Box, you could try the reference counted Rc<T>. You can use Weak pointers for the parent links to avoid keeping them alive:

use std::rc::{Rc,Weak};
pub struct Node<T> {  
    key: T,  
    parent: Option<Weak<Node<T>>>,  
    left: Option<Rc<Node<T>>>,  
    right: Option<Rc<Node<T>>>,  
}

Once this is sorted, you're not using references. Each time you do something like:

let mut parent = origin.parent; //.clone();

where in your version origin.parent is of type Option<Box<Node<T>>>, you're trying to move that Option field out of origin - hence why you had to add the clone() (which clones the node inside the Box, not just the pointer!). However, you don't really want to move out; you just want a reference to it, like:

let parent = &origin.parent;

Or do the None check at the same time:

match origin.parent {
    Some(ref parent_ptr) => { ... },
    None => { ... }
}

I hope this helps!