title: Search for Successor of BST node, "clone to satisfy borrow checker" disaster
body: <p>I am trying to implement a BST in Rust. My struct looks like this:  </p>
  
  <pre><code>pub struct Node&lt;T&gt; {  
      key: T,  
      parent: Option&lt;Box&lt;Node&lt;T&gt;&gt;&gt;,  
      left: Option&lt;Box&lt;Node&lt;T&gt;&gt;&gt;,  
      right: Option&lt;Box&lt;Node&lt;T&gt;&gt;&gt;,  
  }  
  </code></pre>
  
  <p>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:  </p>
  
  <pre><code>//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(&amp;self) -&gt; Option&lt;Box&lt;Node&lt;T&gt;&gt;&gt; {
  
      match self.right {
          Some(ref node) =&gt; Some(node.min()),
          None =&gt; {
              let mut origin = Box::new(self.clone()); //To match types
              let mut parent = origin.parent.clone(); //`Node&lt;T&gt;` not a copy type
  
              loop {
                  let parent_node = match parent.clone() {
                      Some(node) =&gt; node,
                      None =&gt; break,
                  };
                  let right_of_parent = match parent_node.clone().right {
                      Some(node) =&gt; node,
                      None =&gt; break,
                  };
                  if *origin != *right_of_parent {
                      break;
                  }
  
                  origin = parent_node;
                  parent = origin.parent.clone();
              }
              parent
          }
      }
  }  
  </code></pre>
  
  <p>If I remove all the <code>.clone()</code>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?</p>
  
  <p><strong>UPD:</strong><br>
  Wanted to post the solution I ended up with.<br>
  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".<br>
  I considered the answer below, some <a href="http://cglab.ca/~abeinges/blah/too-many-lists/book/" rel="nofollow noreferrer">books</a> and <a href="https://stackoverflow.com/questions/36167160/recursive-data-structures-in-rust/36168919#36168919">relevant answers</a> 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.<br>
  I removed parent field from the structure above and created another structure:  </p>
  
  <pre><code>pub struct Tree&lt;T&gt; {
      root: Option&lt;Box&lt;Node&lt;T&gt;&gt;&gt;,
  }
  </code></pre>
  
  <p>And now I search for parent from the root of the tree. My <code>succ</code> function now looks like this:</p>
  
  <pre><code>fn succ&lt;'a&gt;(&amp;'a self, node: &amp;'a Node&lt;T&gt;) -&gt; Option&lt;&amp;Node&lt;T&gt;&gt; {
      match node.right {
          Some(ref rnode) =&gt; rnode.min(),
          None =&gt; {
              let mut succ = None;
              let mut root = self.root.as_ref();
              loop {
                  root = match root {
                      Some(ref rootnode) =&gt; {
                          match node.key.cmp(&amp;rootnode.key) {
                              Ordering::Less =&gt; {
                                  succ = Some(&amp;***rootnode);
                                  rootnode.left.as_ref()
                              }
                              Ordering::Greater =&gt; rootnode.right.as_ref(),
                              Ordering::Equal =&gt; break,
                          }
                      }
                      None =&gt; break,
                  }
              }
              succ
          }
      }
  }
  </code></pre>