Delete a node and all of its children from a binary tree, without using a tree data structure

Question

Suppose I have an array as an input, say

array = -1 0 0 1 2 1 3 5 5 6 6

(This is actually a parent array representation of a binary tree)

The tree looks like this in this case:

 0
 / \
 1 2
 / \ /
 3 5 4
 / / \
 6 7 8
 / \
9 10

And I have another input, say

input = 1

(this is a node to be deleted from the tree)

What I want to achieve is basically:

1. Delete array[input]
2. Search for the input variable in the remaining array
3. Delete all the elements with value = input
4. Store the indices of the deleted values
5. Search the remaining array for value = indices
6. Delete those elements and store their indices
7. Repeat from step 5 until nothing more can be deleted

This is the algorithm I have thought of to delete a node and all of its children.

So basically for the sample input given above, the output should be:

-1 0 2

I have opted not to use a tree data structure because I feel that constructing the tree from the parent array, then searching for the node and deleting it might be slower (although I may be wrong).

I haven't been able to achieve this in code though, I just have the logic. Whenever I am trying to write the pseudo code, one or more problems in my logic become visible. Which is why I have no concrete code to post here yet. So I have no idea how long this will take.

This is a question for a class assignment and just using a tree data structure will work, but I want to implement a better solution in this case if possible.

Any help is appreciated. No need to give me complete code. Just some pointers would be enough.

• Paul Panzer: I think the problem with your approach is that step 2/5 has linear complexity at each iteration. Of course, you can make a map for children once and for all in linear time and then lookup in constant time, but that would be building a tree structure in all but name.
• Blckknght: Given your representation, what does it mean to remove an item from the tree? If you want to delete 5, what to you put at index 5 in your list? Do you need to update 7 and 8, or can they still point to the removed node afterwards? If "deleting" a node renumbers all the successive node names (by shifting their indexes in the list), you're going to need to do a bunch of cleanup work to make everything else still fit together.
• Yuki.kuroshita: @Blckknght, I don't need to update any values in the tree, but as I said in the question, if I am deleting a node, I need to delete all its children with it. So on deleting 5, 7 and 8 would get deleted too. The cleanup is not that important. What is important in the problem I have been assigned is to delete the node. This operation is to be performed only once, so no need to clean up.
• Yuki.kuroshita: @Paul Panzer, so is there no way to do this in a better way?
• Paul Panzer: Yuki.kuroshita, thinking about it I think there may be a way, I'll try and make an answer. Btw. I think @Blckknght has a point: -1 0 2 doesn't seem to be a valid representation, since by the position equals child id convention it would have to be read as 0: no parent, 1: parent is 0, 2: parent is 2.

Answer 1

Here is an implementation of a slightly modified version of your algorithm.

The difference is that we do not do the purging one level after the other, but instead all in one go. This uses the fact that children always are to the right of their parents, so if we just go through the list once and mark everything that is to delete as we go, we do not miss anything.

This leaves the tree in a non canonical state, because the removed nodes are still there, they just are marked as to remove (by having their parent set at -2).

Therefore I have also added an opotional compression step that removes these nodes and renumbers the remaining ones, so that the remaining nodes are numbered 0, 1, 2, ... without gaps.

from itertools import islice, count
def delete_branch_from_tree(parents, branch_root,
 compress=False, inplace=False):
 n = len(parents)
 if not inplace: # make a copy
 parents = parents[:]
 if branch_root == 0:
 parents[:] = [] if compress else n * [-2]
 return parents
 # -2 will indicate missing nodes
 parents[branch_root] = -2
 for node in range(branch_root+1, n):
 if parents[parents[node]] == -2:
 parents[node] = -2
 if compress: # remove nodes marked as missing, renumber the other ones
 c = count()
 new_number = [None if parent==-2 else next(c) for parent in parents]
 parents[:] = [new_number[parent] for parent in parents if parent != -2]
 # -1 was not in the lookup table (new_number), must fix manually
 parents[0] = -1
 return parents

Demo:

>>> tree = [-1, 0, 0, 1, 2, 1, 3, 5, 5, 6, 6]
>>> 
>>> delete_branch_from_tree(tree, 1)
[-1, -2, 0, -2, 2, -2, -2, -2, -2, -2, -2]
>>> delete_branch_from_tree(tree, 1, compress=True)
[-1, 0, 1]
>>> delete_branch_from_tree(tree, 5)
[-1, 0, 0, 1, 2, -2, 3, -2, -2, 6, 6]
>>> delete_branch_from_tree(tree, 5, compress=True)
[-1, 0, 0, 1, 2, 3, 5, 5]