Why my code run infinity

help
1 
pub fn morris_traversal(root: Option<Rc<RefCell<TreeNode>>>) {
        if root.is_none() {
            return;
        }

        let mut current = root;
        let mut most_right;
        while let Some(current_node) = current.clone() {
            println!("{}", current_node.borrow().value);
            most_right = current_node.borrow().left.clone();
            if most_right.is_some() {
                while most_right.as_ref().unwrap().borrow().right.is_some()
                    && most_right.as_ref().unwrap().borrow().right != current
                {
                    most_right = most_right.unwrap().borrow().right.clone();
                }

                if most_right.as_ref().unwrap().borrow().right.is_none() {
                    most_right.unwrap().borrow_mut().right = current.clone();
                    current = current_node.borrow().left.clone();
                    continue;
                } else {
                    most_right.unwrap().borrow_mut().right = None;
                }
            }

            current = current_node.borrow().right.clone();
        }
    }

 1
  \
  243
    /
   2
    \ 
      42

when it meets a bst like this ,it runs infinity.
"I'm stuck here, the loop isn't terminating. The condition for the loop is that most_right should be the rightmost node of the current_node's left subtree, which should be correct. However, even though the right of the node with value 42 is already None, the loop doesn't exit and continues to execute step-by-step. The values of current_node and most_right are different, but within the while loop, they keep repeating, and they don't change. The loop doesn't exit."

need help! I'm thankful !

2

Try replacing!= with a call using Rc ptr

3

it won't fix this, nice to see your reply.

4 
pub fn morris_traversal(root: Option<Rc<RefCell<TreeNode>>>) {
        if root.is_none() {
            return;
        }

        let mut current = root;
        let mut most_right;
        while let Some(current_node) = current.clone() {
            print!("{} ", current_node.borrow().value);
            most_right = current_node.borrow().left.clone();
            if most_right.is_some() {
                while most_right.as_ref().unwrap().borrow().right.is_some()
                    && most_right.as_ref().unwrap().borrow().right != current
                {
                    most_right = most_right.unwrap().borrow().right.clone();
                }

                if most_right.as_ref().unwrap().borrow().right.is_none() {
                    most_right.unwrap().borrow_mut().right = current.clone();
                    current = current_node.borrow().left.clone();
                    continue;
                } else {
                    most_right.unwrap().borrow_mut().right = None;
                }
            }

            current = current_node.borrow().right.clone();
        }
    }

this can fix it, but I don't understand why the code go infinity.

5

My guess based on looking up Morris traversal is that the inner while is trying to see if this is a real child or a parent thread by comparing to the child's parent, but there's no reason said thread couldn't be further up the tree, so it just keeps chasing children forever.

It's also rather confusing as an implementation, as if I understand it correctly the whole point of threading a tree is that you can just chase the left pointer until it's null to find the left-most node then following the right pointer will give you the in-order traversal. I can't figure what the logic of the current implementation is.

It also modifies a pointer in that inner else branch, I wouldn't expect that in a traversal method.

3 Likes
6

can you show the treenode code and your input test?

7 
pub struct TreeNode {
    pub value: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(value: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode {
            value,
            left: None,
            right: None,
        }))
    }

    pub fn insert(&mut self, value: i32) {
        if value < self.value {
            if let Some(ref mut left) = self.left {
                left.borrow_mut().insert(value);
            } else {
                self.left = Some(TreeNode::new(value));
            }
        } else if value > self.value {
            if let Some(ref mut right) = self.right {
                right.borrow_mut().insert(value);
            } else {
                self.right = Some(TreeNode::new(value));
            }
        }
    }

    pub fn build_bst(values: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if values.is_empty() {
            return None;
        }

        let root = Some(TreeNode::new(values[0]));

        for i in &values[1..] {
            if let Some(ref root_node) = root {
                root_node.borrow_mut().insert(*i);
            }
        }

        root
    }
}

impl PartialEq for TreeNode {
    fn eq(&self, other: &TreeNode) -> bool {
        (match (&self.left, &other.left) {
            (Some(x), Some(y)) => Rc::ptr_eq(x, y),
            (None, None) => true,
            _ => false,
        }) && match (&self.right, &other.right) {
            (Some(x), Some(y)) => Rc::ptr_eq(x, y),
            (None, None) => true,
            _ => false,
        }
    }
}

use crate::TreeNode;
use std::{cell::RefCell, rc::Rc};

pub struct Solution;
#[allow(dead_code)]
impl Solution {
    pub fn morris_traversal(root: Option<Rc<RefCell<TreeNode>>>) {
        if root.is_none() {
            return;
        }


        let mut current = root;
        while let Some(current_node) = current.clone() {
            println!("{}", current_node.borrow().value);
            let mut most_right = current_node.borrow().left.clone();
            if let Some(most_right_node) = most_right {
                while most_right_node.borrow().right.is_some()
                    && most_right_node.borrow().right != current
                {
                    most_right = most_right_node.borrow().right.clone();
                }

                if most_right_node.borrow().right.is_none() {
                    most_right_node.borrow_mut().right = current.clone();
                    current = current_node.borrow().left.clone();
                    continue;
                } else {
                    most_right_node.borrow_mut().right = None;
                }
            }

            current = current_node.borrow().right.clone();
        }
        
    }
}

use leetcode::TreeNode;
fn main() {
    println!("");
    let root1 = TreeNode::build_bst(vec![1,243,3,42]);
    let result = Solution::morris_traversal(root1);
    println!("{:?}", result);
}

the result is:
cargo run

warning: value assigned to most_right is never read
--> leetcode/src/more_challeges/tree/offer_9.rs:21:21
|
21 | most_right = most_right_node.borrow().right.clone();
| ^^^^^^^^^^
|
= help: maybe it is overwritten before being read?
= note: #[warn(unused_assignments)] on by default

warning: leetcode (lib) generated 1 warning
Finished dev profile [unoptimized + debuginfo] target(s) in 0.89s

1
243
^C

8

Thanks, let me try to find the problem out

9 
while most_right_node.borrow().right.is_some()
                    && most_right_node.borrow().right != current
{
  most_right = most_right_node.borrow().right.clone();
}

Here, seem you don't update for most_right_node

1 Like
10

I'm glad to have this problem sloved, thanks a lot !