Help me with Raw pointers in the Tree DS example

#![allow(unused)]
use std::collections::VecDeque;
struct Tree {
    val: u8,
    left: Option<*mut Box<Tree>>,
    right: Option<*mut Box<Tree>>,
}
impl Tree {
    fn new(v: u8) -> Tree {
        Tree {
            val: v,
            left: None,
            right: None,
        }
    }
    
    fn left(&mut self, v: u8) {
        if self.left.is_some() {
            unsafe { (*(*self.left.unwrap())).val = v; }
        } else {
            self.left = Some(&mut Box::new(Tree::new(v)));
        }
    }
    
    fn right(&mut self, v: u8) {
        if self.right.is_some() {
            unsafe { (*(*self.right.unwrap())).val = v; }
        } else {
            self.right = Some(&mut Box::new(Tree::new(v)));
        }
    }
    
    fn traverse(&self) -> Vec<Vec<u8>> {
        let mut res = vec![];
        let mut queue = VecDeque::new();
        queue.push_back(self);
        while !queue.is_empty() {
            let lvl_size = queue.len();
            let mut curr_lvl = vec![];
            for i in 0..lvl_size {
                let node = queue.pop_front().unwrap();
                curr_lvl.push(node.val);
                if node.left.is_some() {
                    queue.push_back(unsafe{&*node.left.unwrap()});
                }
                if node.right.is_some() {
                    queue.push_back(unsafe{&*node.right.unwrap()});
                }
            }
            res.push(curr_lvl);
        }
        res
    }
}

fn main() {
    let mut root = Tree::new(3);
    root.left(1);
    root.right(5);
    // let root = Tree { 
    //     val: 3, 
    //     left: Some(&mut Box::new(Tree {val: 1, left: None, right: None})),
    //     right: Some(&mut Box::new(Tree {val: 5, left: None, right: None}))
    // };
    // let root = Tree {
    //     val: 3, 
    //     left: Some(&mut Box::new(Tree::new(1))),
    //     right: Some(&mut Box::new(Tree::new(5)))
    // };
    println!("{:?}", root.traverse())
}

When I uncomment the below root definitions its working fine but tree created with left(v) & right(v) is throwing a non proper error in playground.

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 1.22s
     Running `target/debug/playground`
/playground/tools/entrypoint.sh: line 11:     8 Killed                  timeout --signal=KILL ${timeout} "$@"

Result with custom tree creation

[[3], [1, 5]]

I can guess it is working because the pointers are freshly created are in Scope & others are dropped. But how can I workout the same definition of Tree.

This line creates a Box, stores a pointer to it, and then immediately drops it. The pointer is now a dangling pointer, pointing to memory that has already been freed:

self.left = Some(&mut Box::new(Tree::new(v)));

You can instead use Box::into_raw to convert the Box<Tree> into a *mut Tree that will not be automatically deallocated. You can store this *mut Tree directly, without the double indirection of *mut Box<Tree>:

struct Tree {
    val: u8,
    left: Option<*mut Tree>,
    right: Option<*mut Tree>,
}

impl Tree {
    fn left(&mut self, v: u8) {
        if self.left.is_some() {
            unsafe { (*self.left.unwrap()).val = v; }
        } else {
            self.left = Some(Box::into_raw(Box::new(Tree::new(v))));
        }
    }
}

(Playground)

You'll probably also want to add a Drop impl that uses Box::from_raw to free the memory when your tree is destroyed.

2 Likes

My question is: do your really want to use raw pointers for that ?
Why not using only Box ?

struct Tree {
    val: u8,
    left: Option<Box<Tree>>,
    right: Option<Box<Tree>>,
}

I guess there is a reason for using raw pointers, could you share it ?

1 Like

Thank you so much for the help