I have class SimpleTree
just basic binary tree:
public class SimpleTree<T extends Comparable<T>> { protected class TreeItem { public T value; public TreeItem left; public TreeItem right; public TreeItem(T value, TreeItem left, TreeItem right) { this.value = value; this.left = left; this.right = right; } public TreeItem(T value) { this(value, null, null); } public T getValue() { return value; } public TreeItem getLeft() { return left; } public TreeItem getRight() { return right; } public void setValue(T value) { this.value = value; } } protected TreeItem item = null; protected int size = 0; // number of elements
And the problem is to write method:
public void delete(TreeItem item, int level) { ... }
Where level
is the level of the elements in some tree (root level == 0). For example level == 1
:
Before: 8 ----- 0 level root / / (size == 6) / 5 10 ----- 1 level / 2 6 11 ----- 2 level and etc. After: 8 ----- 0 level / / (size == 3) / / / 2 11 ----- 1 level
Only LEFT leaf of DELETED elements is saved, if we dont have such -> save the right.
Advertisement
Answer
Your tree seems to be a recursive data structure.
Suppose you want to delete Level N, then traverse down recursively to N- 1
Check at Level N-1 for four cases:
- it has a left and a right child (node 2)
- it has only a left child (node 6)
- it has only a right child (node 10)
- no children (node 7)
When you try to delete Level N You have to fixup the remaining nodes That is why you start at Level N-1, because you need the parent of each node at level N for the fix-up phase.
The four cases above can easily be reduced to:
- If the left child of the left child exists, set the left child to the left child of the left child. (4.left = 4.left.left)
- else if the right child of the left child exists, set the left child to the right child of the left child. (4.left = 4.left.right)
- else NO-OP
For the right child e.g. node 4 it’s exactly the same.
Actually, the fix-up is all you need. Afterwards, let the GC clean up for you and you are done.