+2  A: 

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.

Niki Yoshiuchi
So instead of updating the relevant properties on the nodes, you're creating new nodes altogether and hooking them up? :/
apandit
Exactly. Purely functional languages don't have mutable types so that's your only option. The article the OP references is about zippers, which are a type of tree commonly used in functional programming.
Niki Yoshiuchi
@Niki: Thanks for the explanation. I understood some things, but still have some doubts. Firstly, what is the difference between **imperative programming** and **functional programming**? What are functional data structures? Is a simple binary tree also a functional data structure? Does the previous statement even make sense?
Lazer
Google and wikipedia will probably provide you far more information (and take away a few hours of your life - in a good way) but here are the basics: most programming languages are imperative which means that they rely on statements which change the state of your program. C, C++, Python, Ruby, etc are all imperative or contain imperative features. Functional languages rely on "mathematical" functions and have no state. In other words, there aren't really any variables in the same way that Python has variables. Variables in purely functional languages can't be changed once they are set.
Niki Yoshiuchi
Also, binary trees aren't necessarily purely functional, they are just very easy to represent in a purely functional manner. When someone refers to a purely functional data structure, they are usually referring to an implementation of a particular data structure in a purely functional manner - meaning that updates are non-destructive (instead of change the data structure, they make a copy of it with the relevant changes).
Niki Yoshiuchi
@Niki: thanks a lot!
Lazer