Rust: Tree Structure

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.