binary search tree pseudocode question

9 points
Let T be a BST, where each node x of the tree contains the usual attributes: x.left, x.right, x.parent, x.key.
Suppose we wish to augment the nodes of this tree with the attribute x.depth, which represents the length
of the path from the root of the tree to x. Note that the root node has a depth of 0. Write the pseudo-code
for an algorithm AssignDepth (T) which correctly sets the value of x.depth for each node in the tree rooted
at node T. Justify the runtime of O(n).
Next, update the pseudo-code for Tree-Insert (T, z) so that when a new node z is inserted, the depth
attributes are correctly updated in the tree, and the value of z.depth is set correctly. The runtime of the
new algorithm must be O(h). For reference, the original pseudo-code from class is shown below:
Tree-Insert (T,z)
if T = NIL
return z
else x = T
While x + NIL
y = x
if z.key < x.key x = x.left else x = x.right z.parent = y if z.key