# Insert a node in a binary search tree

The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $$z.p = y$$ instruction does. wouldn't the algorithm work without it?

abr_insert(T, z) //z is the node that must be inserted
{
y = NULL;
x = T.root;
while(x != NULL)
{
y  = x;
if(z.key < x.key)
x = x.left;
else
x = x.right;
}
z.p = y; //here is the instruction that I don't understand
if(y = NULL)
T.root = z;
else if(z.key < y,key)
y.left = z;
else
y.right = z;
}

• The insert algorithm may not use z.p, but it is possible that another BST method relies on the existence and correctness of the value of z.p. It look like z.p stores a pointer to the parent of the node that is to be inserted. May 8 '20 at 16:01

It seems like this algorithm is keeping track of parent pointers. Each node N has three fields: N.left (left child), N.right (right child), and N.p (parent). The variable y is used to keep track of the most recent parent, so when we fall off the tree (i.e. when x == NULL) we can use y as the parent of the new node z.