Tree and Node must own subnodes, but node need just to point to parent, it cannot own parent. #[derive(Debug)] struct Node { data: i32, left: Opti

Tree and Node must own subnodes, but node need just to point to parent, it cannot own parent. #[derive(Debug)] struct Node { data: i32, left: Option<Box<Node>>, right: Option<Box<Node>>, parent: Option<*mut Node>, } impl Node { pub fn new_root(data: i32) -> Self { Node { data, left: None, right: None, parent: None, } } pub fn new_leaf(data: i32, parent: *mut Node) -> Self { Node { data, left: None, right: None, parent: Some(parent), } } } #[derive(Debug)] struct Tree { root: Option<Node>, } impl Tree { pub fn new() -> Self { Tree { root: None } } pub fn insert(&mut self, data: i32) -> bool { match self.root { Some(ref mut node) => Tree::insert_at(node, data), None => { self.root = Some(Node::new_root(data)); true } } } fn insert_at(current_node: &mut Node, data: i32) -> bool { match ( current_node.left.as_deref_mut(), current_node.right.as_deref_mut(), ) { _ if data == current_node.data => false, (Some(left_node), _) if data < current_node.data => Tree::insert_at(left_node, data), (None, _) if data < current_node.data => { let new_node = Node::new_leaf(data, current_node); current_node.left = Some(Box::new(new_node)); true } (_, Some(right_node)) => Tree::insert_at(right_node, data), (_, None) => { let new_node = Node::new_leaf(data, current_node); current_node.right = Some(Box::new(new_node)); true } } } } pub fn main() { let mut tree = Tree::new(); let data = [5, 3, 65, 123, 6, 11, 3, 1, 5, 42]; for i in data { tree.insert(i); } println!("{:?}", tree); }