How to create Tree Zipper using Rust?

Question

I am trying to create a Tree Zipper using Rust. It is inspired by this answer but I am using struct fields instead of Vec for the childs.

I want to have a tree of nodes, e.g.:

    7
   / \
  4   11
 /
2

The point of using a Zipper is that the "current" Node should be mutable. And that this should be implemented without unsafe blocks.

I declared my Node and NodeZipper as below:

#[derive(Debug)]
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn navigate(self) -> NodeZipper {
        NodeZipper {
            node: self,
            parent: None,
        }
    }
}

#[derive(Debug)]
struct NodeZipper {
    node: Node,
    parent: Option<Box<NodeZipper>>,
}

impl NodeZipper {
    fn left(mut self) -> Self {
        let left_child = self.node.left.take().unwrap(); // take() mutates the node
        Self {
            node: *left_child,
            parent: Some(Box::new(self)),
        }
    }

    fn parent(mut self) -> Self {
        let parent = self.parent.take().unwrap();
        Self {
            node: parent.node,
            parent: parent.parent,
        }
    }
}

The problem with the code above is that I use .take() and it mutates the Node, so some data is lost. Is there an alternative way to solve this without using e.g. clone and at least without using unsafe?

Here is a sample run, where I navigate from the root, down to the left child, and then back to the parent (but now the left child is lost).

fn main() {
    let tree = Node {
        value: 7,
        left: Some(Box::new(Node {
            value: 4,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 11,
            left: None,
            right: None,
        })),
    };
    
    let nav = tree.navigate();
    println!("t: {:?}", nav);

    let nav = nav.left();
    println!("t: {:?}", nav);

    let nav = nav.parent();
    println!("t: {:?}", nav);
}

And the output where the left child of the root is lost, when moving back to the parent:

t: NodeZipper { node: Node { value: 7, left: Some(Node { value: 4, left: Some(Node { value: 2, left: None, right: None }), right: None }), right: Some(Node { value: 11, left: None, right: None }) }, parent: None }
t: NodeZipper { node: Node { value: 4, left: Some(Node { value: 2, left: None, right: None }), right: None }, parent: Some(NodeZipper { node: Node { value: 7, left: None, right: Some(Node { value: 11, left: None, right: None }) }, parent: None }) }
t: NodeZipper { node: Node { value: 7, left: None, right: Some(Node { value: 11, left: None, right: None }) }, parent: None }

Answer 1

I mean the obvious error is not putting back the nodes you took. You'll have to store them and put them back when you navigate back.

yes, that is correct. I also lacked understanding of how Zippers should work. But I have got more insight now.

I ended up with a parent() method as below, that also puts back the child node when traversing upwards.

fn parent(mut self) -> Option<Self> {
    match self.parent.take() {
        None => None,
        Some(parent_ref) => {
            let (mut parent, side) = *parent_ref;
            match side {
                ChildSide::Left => {
                   // put back what we took using `take()` while traversing down
                    parent.node.left = Some(Box::new(self.node));
                    Some(Self {
                        node: parent.node,
                        parent: parent.parent,
                    })
                }
                ChildSide::Right => {
                   // put back what we took using `take()` while traversing down
                    parent.node.right = Some(Box::new(self.node));
                    Some(Self {
                        node: parent.node,
                        parent: parent.parent,
                    })
                }
            }
        }
    }
}

With the NodeZipper now declared as:

#[derive(Debug)]
struct NodeZipper {
    node: Node,
    parent: Option<Box<(NodeZipper, ChildSide)>>,
}

#[derive(Debug)]
enum ChildSide {
    Left,
    Right,
}