Rust: Tree Structure

Posted on Edited on In Views: Word count in article: 146 Reading time ≈ 1 mins.

Trying to craft a Tree Structure in Rust.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
use std::{cell::RefCell, rc::Rc};

struct TreeNode {
    val: isize,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: isize) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode {
            val,
            left: None,
            right: None,
        }))
    }

    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>) -> () {
        if let Some(node) = node {
            println!("val is {}", node.borrow().val);
            TreeNode::dfs(&node.borrow().left);
            TreeNode::dfs(&node.borrow().right);
        }
    }
}

fn main() {
    let root_node = TreeNode::new(1);

    root_node.borrow_mut().left = Some(TreeNode::new(2));
    root_node.borrow_mut().right = Some(TreeNode::new(3));

    TreeNode::dfs(&Some(root_node));
}
  • Why Option<T>: Node is allowed to be None in tree.
  • Why Rc<T>: In case of multiple nodes has same child node.
  • Why RefCell<T>: Allow to mutate shared node.

If we can make sure each node has a unique owner, Option<Box<Node<TreeNode>>> is more suitable.