type Link<'a, T> = Option<Box<&'a Node<'a, T>>>;

pub struct Node<'a, T: std::fmt::Debug> {
    data: T,
    left: Link<'a, T>,
    right: Link<'a, T>,
    right_thread: bool,
}

impl<'a, T: std::fmt::Debug> std::fmt::Debug for Node<'a, T> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "Node: {:?}", self.data)
    }
}

pub fn left_most<'a, T: std::fmt::Debug>(n: &'a Node<'a, T>) -> &'a Node<'a, T> {
    let mut _n = n;

    loop {
        match &_n.left {
            Some(left) => _n = left,
            None       => break,
        }
    }

    _n
}

pub fn in_order_traversal<'a, T: std::fmt::Debug>(root: &'a Node<'a, T>) {
    let mut cur: &'a Node<'a, T> = left_most(root);

    loop {
        println!("{:?}", &cur);

        match &cur.right {
            Some(right) => {
                if cur.right_thread {
                    cur = right;
                } else {
                    cur = left_most(right);
                }
            },
            None        => break,
        }
    }
}

fn main() {
    let mut root = Node {
      data: 6,
      left: None,
      right: None,
      right_thread: false
    };

    let mut _node_1_1 = Node {
        data: 3,
        left: None,
        right: None,
        right_thread: true
    };

    let mut _node_1_2 = Node {
        data: 8,
        left: None,
        right: None,
        right_thread: true
    };

    {
        root.left = Some(Box::new(&_node_1_1));
        root.right = Some(Box::new(&_node_1_2));
    }

    {
        _node_1_1.right = Some(Box::new(&root));
        _node_1_1.left = Some(Box::new(&root));
    }

    { in_order_traversal(&root); }
}