Cormen problem 13-1 part d I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution:
PERSISTENT-TREE-INSERT(T,z)
y= T.nil
x=T.root
while x != T.nil
   y=x
   if z.key &lt; x.key
       x = x.left 
   else x = x.right
if y == T.nil
    T'.root = z
    return T'
else if z.key = y.key
    y'=copy(y)
    y'.left = z
    z.p = y'
else y'= copy(y)
     y'.right=z
     z.p = y'
x = y'
while x.p != T.nil
  if x.key &lt; x.p.key
     x' = copy(x.p)
     x'.left = x
     x.p = x'
 else x' = copy(x.p)
    x'.right = x
    x.p = x'
T'.root = x
return T'

Now the copy procedure is :
copy(x)
 w.p = x.p
 w.right= x.right
 w.left = x.left
 w.key = x.key
 return w

Now this means that I only need to copy the node that is going to be the father of the key that I'm adding and its ancestors. The book however says that additional copying is needed just because we have a reference to the parent, but I don't see it. If someone could point me in the right direction I would be much grateful.
For reference this is the exercise:
During the course of an algorithm, we sometimes find that we need to maintain past
versions of a dynamic set as it is updated. We call such a set persistent. One way to
implement a persistent set is to copy the entire set whenever it is modified, but this
approach can slow down a program and also consume much space. Sometimes, we
can do much better.
Consider a persistent set S with the operations INSERT, DELETE, and SEARCH,
which we implement using binary search trees as shown in Figure 13.8(a). We
maintain a separate root for every version of the set. In order to insert the key 5
into the set, we create a new node with key 5. This node becomes the left child
of a new node with key 7, since we cannot modify the existing node with key 7.
Similarly, the new node with key 7 becomes the left child of a new node with
key 8 whose right child is the existing node with key 10. The new node with key 8
becomes, in turn, the right child of a new root r0 with key 4 whose left child is the
existing node with key 3. We thus copy only part of the tree and share some of the
nodes with the original tree, as shown in Figure 13.8(b).
d) Suppose that we had included the parent attribute in each node. In this case,
PERSISTENT-TREE-INSERT would need to perform additional copying. Prove
that PERSISTENT-TREE-INSERT would then require .n/ time and space,
where n is the number of nodes in the tree.
Alright, it was all in the diagram:

We need to copy the descendants of the nodes in the path to make sure we don't end up with a single node having two parents