Cannot borrow immutable borrowed content as mutabl

I want to implement a binary tree. My main language is C++ so the code is probably not idiomatic Rust, but compiling the following code:

use std::rc::Rc;

struct Node {
    left: Option<Rc<Node>>,
    right: Option<Rc<Node>>,
    data: String,
}


impl Node {
    fn new(_data: String) -> Node {
        Node {
            data : _data.clone(),
            left : None,
            right : None,
        }
    }

    fn insert_left(&mut self, mut node: &Rc<Node>) {
        self.left = Some(node.clone());
    }

    fn insert_right(&mut self, mut node: &Rc<Node>) {
        self.left = Some(node.clone());
    }
}

fn main() {
    let mut root = Rc::new(Node::new(String::from("root")));
    let mut left = Rc::new(Node::new(String::from("left")));
    root.insert_left(&left);
}

I have the compilation error:

error: cannot borrow immutable borrowed content as mutable
  --> so.rs:31:9
   |
31 |         root.insert_left(&left);
   |         ^^^^

error: aborting due to previous error

I can't understand what is wrong here. After some try-mistake iterations I found out that problem lies in the insert_left() function: if self is an immutable reference, then it compiles with commented out content, but an immutable reference does not allow my to accomplish my goal.

Here's a MCVE of your problem:

use std::rc::Rc;

struct Node;

impl Node {
    fn insert_left(&mut self) {}
}

fn main() {
    let root = Rc::new(Node);
    root.insert_left();
}

You can arrive at an example like this by removing as much code as possible while still getting the same error. This process helps tremendously to build understanding of the problem.

The problem is that Rc disallows mutation of any kind. As stated in the documentation:

Shared pointers in Rust disallow mutation by default, and Rc is no exception. If you need to mutate through an Rc, use Cell or RefCell.

Therefore, there's no way to go from a Rc<Foo> to a &mut Foo, which would be needed to call the insert_left method.

As documented, you can use one of the types that allows interior mutability, such as a Cell or RefCell. These function a bit like a mutex, but are not valid for multithreaded scenarios. They ensure that only one mutable reference to a value is available at a time, a key component of Rust's safety.

If you don't need the functionality of Rc's sharing, you can just move to having an Option<Box<Node>> as well.