11

I am trying to solve some Leetcode problems with Rust. However, I ran into some difficulties with LeetCode's TreeNode implementation.

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

// TreeNode data structure
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

If I want to do an inorder traversal, how to unwrap the TreeNode's Option<Rc<RefCell<TreeNode>>> object, access its .val .left .right and pass them as inputs into a recursive function?

I have tried:

pub struct Solution;

impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ret: Vec<i32> = vec![];
        match root {
            Some(V) => Solution::helper(&Some(V), &mut ret),
            None => (),
        }

        ret
    }

    fn helper(node: &Option<Rc<RefCell<TreeNode>>>, ret: &mut Vec<i32>) {
        match node {
            None => return,
            Some(V) => {
                // go to the left branch
                Solution::helper(
                    (*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
                        .into_inner()
                        .left,
                    ret,
                );
                // push root value on the vector
                ret.push(Rc::try_unwrap(Rc::clone(V)).unwrap_err().into_inner().val);
                // go right branch
                Solution::helper(
                    (*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
                        .into_inner()
                        .right,
                    ret,
                );
            }
        }
    }
}

fn main() {}

(Playground)

The compiler complains:

error[E0308]: mismatched types
  --> src/lib.rs:42:21
   |
42 | /                     (*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
43 | |                         .into_inner()
44 | |                         .left,
   | |_____________________________^ expected reference, found enum `std::option::Option`
   |
   = note: expected type `&std::option::Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>`
              found type `std::option::Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>`
help: consider borrowing here
   |
42 |                     &(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
43 |                         .into_inner()
44 |                         .left,
   |

But if I try the suggestion, it complains as well:

error[E0507]: cannot move out of an `Rc`
  --> src/lib.rs:42:22
   |
42 |                     &(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot move out of an `Rc`

error[E0507]: cannot move out of data in a `&` reference
  --> src/lib.rs:42:22
   |
42 |                     &(*Rc::try_unwrap(Rc::clone(V)).unwrap_err())
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                      |
   |                      cannot move out of data in a `&` reference
   |                      cannot move
0

1 Answer 1

7

Unwrap and access T from an Option<Rc<RefCell<T>>>

You really don't want to try to remove the value from the Option, the Rc or the RefCell via unwrap / try_unwrap / into_inner. Instead, pattern match on the Option and then call borrow on the RefCell to get a reference to the T.

Additionally:

  1. Use if let instead of a match statement when you only care about one arm.
  2. Variables use snake_case. V is not an appropriate name.
  3. There's no need to use a struct here, or to define the helper function publicly. A plain function and a nested function are simpler and exposes less detail.
  4. There's no need to provide an explicit type when constructing ret.
pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    fn helper(node: &Option<Rc<RefCell<TreeNode>>>, ret: &mut Vec<i32>) {
        if let Some(v) = node {
            let v = v.borrow();

            helper(&v.left, ret);
            ret.push(v.val);
            helper(&v.right, ret);
        }
    }

    let mut ret = vec![];

    if let Some(v) = root {
        helper(&Some(v), &mut ret);
    }

    ret
}

Personally, I'm not a fan of being forced to construct the Some, so I'd probably reorganize the code, which also allows me to stick it as a method on TreeNode:

impl TreeNode {
    pub fn inorder_traversal(&self) -> Vec<i32> {
        fn helper(node: &TreeNode, ret: &mut Vec<i32>) {
            if let Some(ref left) = node.left {
                helper(&left.borrow(), ret);
            }

            ret.push(node.val);

            if let Some(ref right) = node.right {
                helper(&right.borrow(), ret);
            }
        }

        let mut ret = vec![];
        helper(self, &mut ret);
        ret
    }
}

See also:

5
  • just wondering. For the purpose of this exercise TreeNode could be written using just Box instead Rc<RefCell<..>> right? If the answer is yes, is this version better for trees? Please let me know if this comment worth a brand new question. Apr 8, 2022 at 7:43
  • @RaydelMiranda could be? Sure, as far as I can see. "Better" isn't a well-formed question. They have different capabilities and tradeoffs. If you need a capability that only one form provides, then that one is better for your case.
    – Shepmaster
    Apr 8, 2022 at 12:39
  • I see. About the "Better" part of the question, sorry I don't explain my self, I was meaning in the context of this very same exercise. I have seen this exercise in sites like LeetCode and I have seen the same data structure implemented in Rust using Box or Rc/RefCell. I am relatively new to Rust and things like that caught my attention. In this exercise, there is no need for share values or mutate the node values (the perfect use case for Rc-RefCell), so, perhaps due to me having so little experience with Rust I was missing something, perhaps related with performance, I don't know. Apr 9, 2022 at 2:39
  • I investigate further, and found this article, about inner-mutability, where you can find an example of a Graph implementation. In a Graph, one same node can be adjacent to several nodes, so in this case using Rc with RefCell have more sense since two or more nodes might "share" the same neighbors. In a tree (binary in this case), one and only one node can be either the left or the right child of a parent, so, in my humble opinion using Box over Rc/RefCell for trees is less error prone and better for clarity and readability. ricardomartins.cc/2016/06/08/interior-mutability Apr 9, 2022 at 3:45
  • @RaydelMiranda yes, I'd also probably use a Box for this problem.
    – Shepmaster
    Apr 19, 2022 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.