Effects of changing a node in a binary tree

Question

Suppose I want to change the orange node in the following tree.

So, the only other change I'll need to make is in the left pointer of the green node.

The blue node will remain the same.

Am I wrong somewhere? Because according to this article (that explains zippers), even the blue node needs to be changed.

Similarly, in this picture (recolored) from the same article, why do we change the orange nodes at all (when we change node x)?

Answer 1

In an imperative language you are correct, only the green node needs to be changed. However for purely functional data structures this is not the case. In order to change the orange node you need to change the green node. Because you changed the green node, you then need to change the blue node (and so on). Actually the word change is incorrect, you are really copying the relevant data and creating a new node. So The blue node isn't being changed so much as a new blue node (which points to the new green node) is being created.

Doing so maintains persistence, meaning that you can store all previous states of the tree. If you wanted to store the tree before changing the orange node and after changing the orange node, you'd need change both the green and blue - otherwise both would be copies of the same tree.

In the second case, the same thing applies, only now you also need to change parent pointers. Since you've changed the root node, all the orange nodes need to have their parent pointers set to point to their new parents.

Edit: to clarify a bit, think about it like this. In a purely functional language you can't modify anything, you can only create new nodes or copy them. So when you want to change the orange node, you actually make a copy of it with different data (the "change"). Now you need the green node to point to the orange node, which requires you to create a new orange node - this one pointing to the new green node. The same is true for the blue node.