keeping binary search tree node depth propery updated

Question

How can I keep the depth property of a binary search tree's node updated after something is deleted?

I'm thinking that for the case where I delete a node with one child, then I can set the depth of every node under the parent of the node deleted to (original depth - 1).

However, I can not think of a good way to keep depth updated when I am deleting a node that had two children.

For the case of deleting a node with two children, my delete method either moves the left-most node in the right subtree, or the right-most node in the left subtree, up to the node that I am deleting, depending on which path is shorter.

I am not looking for code, just a general game plan or pseudo code

Answer 1

I think the problem seemed more complicated to me than it really was. After drawing a few trees, and applying the delete function on a node with two children (on paper), I noticed that only one node really changes in depth -- the node that replaces the deleted node.

I set the depth of node N, that replaced the node R, with R's depth.

Answer 2

The data structure that represents depth aggregation is a histogram, i.e. a dictionary mapping from depth to count. A deletion of a leaf is a single update to the histogram, while a deletion of a non-leaf is an exercise left to the reader.