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.

CodePudding user response：

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:

1. it has a left and a right child (node 2)
2. it has only a left child (node 6)
3. it has only a right child (node 10)
4. 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.