OCaml - setting reference to next node in inorder (binary tree)

Question

type 'a tree= | Empty| Node of 'a * 'a tree* 'a tree* 'a tree ref;;

We would like to set for every node tree ref to next node in inorder;

For example

Node (1, Node(2, Empty, Empty, ref Empty), Node(3, Empty, Empty, ref Empty), ref Empty) )
The result is:

Node (1, Node(2, Empty, Empty, content = {Node (1....) }).....

Answer 1

It's not hard: you do an inorder traversal, while passing around (and returning) the reference contained in the previous node. When you get to a given node, you set the reference of the previous node to the current node. If each node is assigned to the reference of the previous one, that means every node's reference contains the next node.

On the example, the inorder traversal goes through the tree in this order: 2 1 3

When you are at node 2, you return its ref to the caller, which is node 1. When you arrive at node 1, you set the ref of node 2 to point to node 1, and you pass the ref of node 1 to node 3. When you are at node 3, you set the ref of node 1 to point to node 3.

You need to decide what to do for the first node (allocate a dummy reference to start the process) and the last node (presumably, set its reference to Empty, although sometimes it might be useful to set it to the first node).

I have working code (15 lines). I won't post it because that would spoil the presumed assigment.