What is the paradigmatic way to create a Rust tree with a parent pointer? [duplicate]

Question

I need to define a binary search tree where each node has access to the parent:

enum Tree<'a> {
    Leaf,
    Node {
        left: Box<Tree<'a>>,
        right: Box<Tree<'a>>,
        parent: &'a Tree<'a>,
        data: u64,
    }
}

impl <'a> Tree<'a> {
    pub fn new(data: u64, parent: &'a Tree) -> Tree<'a> {
        Tree::Node {
            left: Box::new(Tree::Leaf),
            right: Box::new(Tree::Leaf),
            parent,
            data
        }
    }
    pub fn insert_at_left_leaf(&'a mut self, data: u64) {
        match *self {
            Tree::Leaf => panic!("Leaf has no children"),
            Tree::Node {ref mut left, ..} => {
                **left = Tree::new(data, self);
            }
        }
    }
}

fn main() {
    let parent = Tree::Leaf;
    let mut t = Tree::Node {
        left: Box::new(Tree::Leaf),
        right: Box::new(Tree::Leaf),
        parent: &parent,
        data: 1u64
    };
    t.insert_at_left_leaf(2);
}

playground

However, I get the following compilation error:

error[E0502]: cannot borrow `*self` as immutable because `self.left` is also borrowed as mutable
  --> src/main.rs:24:42
   |
23 |             Tree::Node {ref mut left, ..} => {
   |                         ------------ mutable borrow occurs here
24 |                 **left = Tree::new(data, self);
   |                                          ^^^^ immutable borrow occurs here
25 |             }
26 |         }
   |         - mutable borrow ends here

What is the paradigmatic way to do this in safe Rust? Specifically, when I insert a new node as the leaf of an existing node, I do not want to re-allocate space for it. There is already space allocated for the Leaf and I want to simply overwrite it with the new node.

Trillium

That's not a tree. If it has a parent pointer, it's a graph, not a tree. – Vagary

I disagree. Having a parent pointer is an implementation detail. Ultimately what makes the data structure a tree or a graph is the API it exposes (i.e. from the user's standpoint are their cycles or not in the data structure?). – Trillium

The compiler doesn't care that you are only exposing half of the graph - the concept of ownership within a graph is not easily expressible and that's what the compiler is telling you. – Vagary

@Vagary This is a special case of a graph. For that reason I don't think it should be closed as duplicate: A solution that will work in this case (e.g. using Rc for child pointers and weak references for parent pointers) won't necessarily work for general graphs. – Detoxify

@Detoxify the duplicate target also has a node with children and parents and an answer suggests using Rc, just as you suggest; why do you think that's not a valid target? – Vagary

It is still unclear to me why what I am doing is unsafe. It seems perfectly valid for a child to have a reference to the parent and in turn be owned by the parent. The child can only go out of scope when the parent relinquishes ownership of it and there is no problem of dangling pointers. – Trillium

@Vagary I looked at the other duplicate which said that it is impossible in safe Rust. By the way, the Rust documentation refers to a tree with parent pointers as a tree, not a graph: doc.rust-lang.org/std/rc/struct.Weak.html – Detoxify

I didn't say it was unsafe. You can totally have a value contain a reference to itself, so long as you never modify or move it, which is not what most people want. See Why can't I store a value and a reference to that value in the same struct? for details — your parent would store a child which would have a reference to the parent, thus you are storing a reference to yourself. – Vagary

Remember that safe Rust is only capable of expressing a certain subset of the programs that are actually safe. Use of the unsafe keyword allows the programmer to say "no, I guarantee that this code is safe by Rust's safety rules even though the compiler cannot see that it is". You cannot write code that is actually unsafe regardless of how many keywords you add. – Vagary

"You cannot write code that is actually unsafe regardless of how many keywords you add." - that's just not true. In an unsafe block you can write code that dereferences unallocated memory which is absolutely unsafe. For example: unsafe { let p = 1; let q = p as *const i64; println!("{:?}", *q); } – Trillium

@Trillium you are correct; I used ambiguous phrasing — I'm sorry I confused the issue. I meant to say something closer to: "You must never write code that is actually unsafe regardless of how many keywords you add." – Vagary

I don't agree that this is a duplicate of either of the marked questions. I've nominated for reopening. – Suprematism

@user1413793: "It seems perfectly valid for a child to have a reference to the parent and in turn be owned by the parent." Which do you drop first? If you drop the parent first, the child has a dangling pointer to it when it gets dropped. If you drop the child first, the parent has a dangling pointer to it when it gets dropped. Neither of these are situations Rust will allow in safe code. – Dominations

By rust's ownership rules, only the parent may drop the child as the parent owns it. So, the parent (or whoever owns the parent) can safely drop the left (or right) child with no dangling pointers. Because the child only has a reference to the parent, this is perfectly okay. – Trillium