Traverse through binary tree

Radhika Gokani 0
Viewed 50
use std::cell::RefCell;
use std::rc::Rc;

#[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,
        }
    }

    pub fn invalid_path_error(self) {
        panic!("Invalid path");
    }

    pub fn insert(&mut self, directions: &[&str], val: i32) {
        let mut cur_node = &mut None;

        let l = directions.len();

        if directions[0] == "left" {
            cur_node = &mut self.left;
        }
        if directions[0] == "right" {
            cur_node = &mut self.right;
        }

        for dir in &directions[1..] {
            let mut n;

            if *dir == "left" {
                if let Some(z) = cur_node {
                    n = &mut z.borrow_mut().left;
                } else {
                    panic!("Invalid path");
                }
            }
            if *dir == "right" {
                if let Some(z) = cur_node {
                    n = &mut z.borrow_mut().right;
                } else {
                    panic!("Invalid path");
                }
            }

            cur_node = n;
        }

        //cur_node = Some(Rc::new(RefCell::new(TreeNode::new(2))));
    }
}

I am trying to learn rust by solving some leet code questions. I am trying to implement insert function for binary tree. This is the struct given in leet code. I am trying to implement insert by pass list of strings for path For eg. go left , right , left etc. After traversing at the end I will add new node. I am trying to use cur node as a temp pointer and want to change it with each string. But every time I get this error - " temporary value dropped while borrowed consider using a let binding to create a longer lived value ". How can I fix this and implement insert ?

cargo check -

enter image description here

binary-tree rust
1 Answers

Here's a solution that replaces Rc<RefCell<_>> with Box<_>. Generally you only need to reach for Rc when multiple people will want ownership over the underlying data. In this case, each node is only owned by one other node, so Box is preferable.

This solution iterates through the tree to find the last node, then uses the last direction to assign to the correct child node. No checks are implemented to make sure that the nodes along the path exist or that an existing node isn't being overwritten.

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}

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

    pub fn insert(&mut self, directions: &[&str], val: i32) {
        let mut cur_node = self;

        let len = directions.len();
        let mut directions = directions.into_iter().copied();
        for direction in directions.by_ref().take(len - 1) {
            let child_node = match direction {
                "left" => &mut cur_node.left,
                "right" => &mut cur_node.right,
                _ => panic!("invalid direction {direction}"),
            };
            cur_node = child_node.as_mut().expect("invalid path").as_mut();
        }

        let new_node = Some(Box::new(TreeNode::new(val)));
        match directions.next().unwrap() {
            "left" => cur_node.left = new_node,
            "right" => cur_node.right = new_node,
            direction @ _ => panic!("invalid direction {direction}"),
        }
    }
}

fn main() {
    let mut tree = TreeNode::new(0);
    tree.insert(&["left"], 1);
    tree.insert(&["right"], 2);
    tree.insert(&["left", "left"], 2);
    tree.insert(&["right", "left"], 3);
    println!("{:#?}", tree);
}

Prints

TreeNode {
    val: 0,
    left: Some(
        TreeNode {
            val: 1,
            left: Some(
                TreeNode {
                    val: 2,
                    left: None,
                    right: None,
                },
            ),
            right: None,
        },
    ),
    right: Some(
        TreeNode {
            val: 2,
            left: Some(
                TreeNode {
                    val: 3,
                    left: None,
                    right: None,
                },
            ),
            right: None,
        },
    ),
}
BallpointBen0
Related