В императивном языке вы правы, нужно изменить только зеленый узел. Однако для чисто функциональных структур данных это не так. Чтобы поменять оранжевый узел, нужно поменять зеленый узел. Поскольку вы изменили зеленый узел, вам нужно изменить синий узел (и так далее). На самом деле слово change неверно, вы действительно копируете соответствующие данные и создаете новый узел. Таким образом, синий узел изменяется не так сильно, как новый синий узел (который указывает на новый зеленый узел).
При этом сохраняется постоянство , что означает, что вы можете хранить все предыдущие состояния дерева. Если вы хотите сохранить дерево до изменения оранжевого узла и после изменения оранжевого узла, вам нужно будет изменить и зеленый, и синий - иначе оба будут копиями одного и того же дерева.
Во втором случае применяется то же самое, только теперь вам также нужно изменить указатели родителей. Поскольку вы изменили корневой узел, все оранжевые узлы должны иметь свои родительские указатели, указывающие на их новых родителей.
Редактировать: чтобы уточнить немного, подумайте об этом так. На чисто функциональном языке вы ничего не можете изменить, вы можете только создавать новые узлы или копировать их. Поэтому, когда вы хотите изменить оранжевый узел, вы фактически делаете его копию с другими данными («изменение»). Теперь вам нужно, чтобы зеленый узел указывал на оранжевый узел, что требует от вас создания нового оранжевого узла - этот указывает на новый зеленый узел. То же самое верно для синего узла.