Is this n-ary weighted tree implementation idiomatic rust? I find it too repetitive

Question

Context and description of the encountered problem

Currently I'm learning the Rust Programming Language and last weekend I found myself implementing a generic n-Ary weighted tree data structure whose Nodes are of type N and edges of type E.

I was browsing the std docs and found the Iterator trait and was tempted to implement it for this datastructure. But there is a caveat: There are several reasonable ways to traverse a tree datastructure that I wanted to implement:

• preorder
• postorder
• inorder

Additionally, I want one iterator to yield &references and one to yield exclusive references &mut for all of the previously named traversal options thus having to implement 6 Iterators where 3 just differ in mutability from the other 3 for my data structure. Furthermore I want to stay away from macros if possible (although I can imagine them to be helpful here)!

Naturally this leads to some (minimal? for my taste a bit too much) code duplication.

Current Implementation

The generic node data structure has two relevant methods:

pub fn traverse_ref(&self, traverse: Traverse) -> Box<dyn Iterator<Item = &Self> + '_>

pub fn traverse_mut(&mut self, traverse: Traverse) -> Box<dyn Iterator<Item = &mut Self> + '_>

where Traverse is an enum holding all supported ways of traversing the tree.

They return boxes of the proper iterator-structs Traversal<'t, N, E, M> and TraversalMut<'t, N, E, M>, respectively, where N and E are the generics of the tree and M is a type which specifies which kind of traversal takes place.

My attempt at reducing duplication lies in the fact that I added a Traveller trait whose methods handle the various kinds of iteration thus having to only call the proper method of that trait in both of my Iterator implementations for a given traversal method.

This seems repetetive.

API example (main.rs)

mod tree;

fn main() {
    use std::num::NonZeroU8;
    use tree::Node;

    let mut tree = Node::new(NonZeroU8::new(1));

    tree.add_children(NonZeroU8::new(2), true);
    tree.add_children(NonZeroU8::new(3), false);

    tree.get_children_mut()[0]
        .0
        .add_children(NonZeroU8::new(4), true);
    tree.get_children_mut()[0]
        .0
        .add_children(NonZeroU8::new(5), false);

    for node in tree.traverse_ref(tree::Traverse::PreOrder) {}
}

tree.rs

Note that the actual implementations of the traversal algorithms were elided to increase readability as they don't matter for the faced problem. Instead I provided a simple todo!().

use std::marker::PhantomData;

mod internal {
    pub trait Sealed {}
}

#[derive(Debug)]
pub struct Node<N, E> {
    value: N,
    children: Vec<(Node<N, E>, E)>,
}

impl<N, E> Node<N, E> {
    pub fn new(value: N) -> Self {
        Self {
            value,
            children: vec![],
        }
    }

    pub fn add_children(&mut self, value: N, edge: E) {
        self.children.push((Node::new(value), edge));
    }

    pub fn get_children_mut(&mut self) -> &mut Vec<(Self, E)> {
        &mut self.children
    }

    pub fn get_value_mut(&mut self) -> &mut N {
        &mut self.value
    }

    pub fn set_value(&mut self, new_value: N) {
        self.value = new_value;
    }

    pub fn traverse_ref(&self, traverse: Traverse) -> Box<dyn Iterator<Item = &Self> + '_> {
        match traverse {
            Traverse::InOrder => Box::new(Traversal::<N, E, InOrder>::new(self)),
            Traverse::PostOrder => Box::new(Traversal::<N, E, PostOrder>::new(self)),
            Traverse::PreOrder => Box::new(Traversal::<N, E, PreOrder>::new(self)),
        }
    }

    pub fn traverse_mut(&mut self, traverse: Traverse) -> Box<dyn Iterator<Item = &mut Self> + '_> {
        match traverse {
            Traverse::InOrder => Box::new(TraversalMut::<N, E, InOrder>::new(self)),
            Traverse::PostOrder => Box::new(TraversalMut::<N, E, PostOrder>::new(self)),
            Traverse::PreOrder => Box::new(TraversalMut::<N, E, PreOrder>::new(self)),
        }
    }
}

#[derive(Debug)]
pub enum Traverse {
    PreOrder,
    PostOrder,
    InOrder,
}

pub trait TraverseMethod: internal::Sealed {}

#[derive(Debug)]
struct PreOrder {}
impl internal::Sealed for PreOrder {}
impl TraverseMethod for PreOrder {}

#[derive(Debug)]
struct InOrder {}
impl internal::Sealed for InOrder {}
impl TraverseMethod for InOrder {}

#[derive(Debug)]
struct PostOrder {}
impl internal::Sealed for PostOrder {}
impl TraverseMethod for PostOrder {}

#[derive(Debug)]
pub struct Traversal<'t, N, E, M>
where
    M: TraverseMethod,
{
    tree: &'t Node<N, E>,
    _marker: PhantomData<M>,
}

impl<'t, N, E, M> Traversal<'t, N, E, M>
where
    M: TraverseMethod,
{
    fn new(tree: &'t Node<N, E>) -> Self {
        Self {
            tree,
            _marker: PhantomData {},
        }
    }
}

#[derive(Debug)]
pub struct TraversalMut<'t, N, E, M>
where
    M: TraverseMethod,
{
    tree: &'t mut Node<N, E>,
    _marker: PhantomData<M>,
}

impl<'t, N, E, M> TraversalMut<'t, N, E, M>
where
    M: TraverseMethod,
{
    fn new(tree: &'t mut Node<N, E>) -> Self {
        Self {
            tree,
            _marker: PhantomData {},
        }
    }
}

trait Traveller {
    type Item;

    fn travel_preorder(&mut self) -> Option<Self::Item> {
        todo!()
    }

    fn travel_postorder(&mut self) -> Option<Self::Item> {
        todo!()
    }

    fn travel_inorder(&mut self) -> Option<Self::Item> {
        todo!()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, PreOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, PreOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_preorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, PreOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, PreOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_preorder()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, PostOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, PostOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_postorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, PostOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, PostOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_postorder()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, InOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, InOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_inorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, InOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, InOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_inorder()
    }
}