The last part of the picture doesn't make sense to me

Question about the task

Under discussion

I don't understand the process. If you remove node 3, then wouldn't the next added node be the first available left child (of 1)? Why does the next added node go to 9 instead of 1? FYI, I added a helper method called printTree() to help troubleshoot. Another question: in all my methods, traversing the tree is basically duplicate code. Is there a way to pull this duplicate code out to another method and still retain the functionality of add(), remove(), getParent(), etc?

We can add elements to the tree. Now let's work on deleting them:

Implement the remove(Object o) method, which will remove the tree node whose name was passed as an argument.

The method must throw an UnsupportedOperationException if the argument is not a String.

If there are multiple tree nodes with the passed name, delete only the first node found.

Don't forget to compare your tree's behavior with the following picture:

What happens if you remove nodes 3, 4, 5, and 6 from the tree, and then try to add a new node?

In this case, nodes 1 and 2 should regain the ability to have descendants (you might have to make changes to the add() method).

Requirements:

After using the remove method to remove the last added node from the tree, the size method should return N-1.
After removing the second node added to the tree, the size method should return N/2 + 1 (if N>2 and a power of two), where N is the size of the tree before removal.
The remove() method must throw an UnsupportedOperationException if the argument is not a String.
If no nodes can have descendants, you must restore their ability to do so.

package com.codegym.task.task20.task2028; import java.util.List; public class Solution { public static void main(String[] args) { List<String> list = new CustomTree(); for (int i = 1; i < 16; i++) { list.add(String.valueOf(i)); } System.out.println("The list size is " + list.size()); System.out.println("The expected parent is 3. The actual parent is " + ((CustomTree) list).getParent("8")); System.out.println("The expected parent is null. The actual parent is " + ((CustomTree) list).getParent("20")); ((CustomTree) list).printTree(); list.remove("3"); System.out.println("The expected parent is null. The actual parent is " + ((CustomTree) list).getParent("8")); ((CustomTree) list).printTree(); } }

Comments (7)

Popular
New
Old

You must be signed in to leave a comment

JianQiu Hwang

Level 35 , Washington

16 May 2020, 03:15

You should change your `add()` function for restore all leaves node's `availableToAddLeftChildren` and `availableToAddLeftChildren` to true. Here is my solution:

public boolean add(String s) {
    Entry newNode = new Entry(s);
    Queue<Entry> q = new LinkedList<>();
    q.add(root);
    ArrayList<Entry> leaves = new ArrayList<>();

    while (!q.isEmpty()) {
        Entry node = q.poll();
        if (node.availableToAddLeftChildren) {
            node.leftChild = newNode;
            node.availableToAddLeftChildren = false;
            newNode.parent = node;
            return true;
        } else if (node.availableToAddRightChildren) {
            node.rightChild = newNode;
            node.availableToAddRightChildren = false;
            newNode.parent = node;
            return true;
        } else {
            if (node.leftChild == null && node.rightChild == null) {
                leaves.add(node);
            } else {
                if (node.leftChild != null) q.add(node.leftChild);
                if (node.rightChild != null) q.add(node.rightChild);
            }
        }
    }
    // RESTORE ALL LEAVES NODE
    for (Entry entry : leaves) {
        entry.availableToAddRightChildren = true;
        entry.availableToAddLeftChildren = true;
    }
    return add(s);
}

Andrew

Level 29 , Seattle, United States

3 July 2019, 20:19

I think I'm starting to understand. The next added node will go to the first available child of the lowest limb on the tree, even though there may be available children closer to the root. How do you manage that? Here's my add method:

@Override
   public boolean add(String s) {
       Entry<String> child = new Entry<String>(s);

       Queue<Entry<String>> queue = new LinkedList<>();
       queue.add(root);

       while (!queue.isEmpty()) {
           Entry<String> tempNode = queue.poll();

           if (tempNode.leftChild != null) queue.add(tempNode.leftChild);
           else {
               tempNode.leftChild = child;
               child.parent = tempNode;
               return true;
           }

           if (tempNode.rightChild != null) queue.add(tempNode.rightChild);
           else {
               tempNode.rightChild = child;
               child.parent = tempNode;
               return true;
           }
       }

       return false;
   }

Djole

Level 41 , Belgrade, Serbia

7 July 2019, 22:08

this is my add method @Override public boolean add(String s) { Queue<Entry<String>> queue = new LinkedList<>(); boolean flag = false; queue.add(root); List<Entry<String>> temp = new ArrayList<>(); List<Entry<String>> immutableList = new ArrayList<>(); while (!queue.isEmpty()) { Entry<String> currentNode = queue.poll(); currentNode.checkChildren(); if (currentNode.isAvailableToAddChildren()) { if (currentNode.availableToAddLeftChildren){ currentNode.leftChild = new Entry<>(s); currentNode.leftChild.parent = currentNode; return true; } else if (currentNode.availableToAddRightChildren) { currentNode.rightChild = new Entry<>(s); currentNode.rightChild.parent = currentNode; return true; } } else { if (currentNode.leftChild != null){ queue.offer(currentNode.leftChild); } if (currentNode.rightChild != null){ queue.offer(currentNode.rightChild); } if(currentNode.leftChild == null && currentNode.rightChild == null) { flag = true; temp.add(currentNode); immutableList = Collections.unmodifiableList(temp); } } } if(flag) { immutableList.get(0).leftChild = new Entry<>(s); immutableList.get(0).leftChild.parent = immutableList.get(0); return true; } return false; }

Djole

Level 41 , Belgrade, Serbia

7 July 2019, 22:08

and this is remove @Override public boolean remove(Object o) throws UnsupportedOperationException{ if(!(o instanceof String)){ throw new UnsupportedOperationException(); } Queue<Entry<String>> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { Entry<String> currentNode = queue.poll(); if (currentNode.leftChild != null) { if (currentNode.leftChild.elementName.equals(o)){ currentNode.leftChild.parent.availableToAddLeftChildren = false; currentNode.leftChild = null; return true; } queue.offer(currentNode.leftChild); } if (currentNode.rightChild != null) { if (currentNode.rightChild.elementName.equals(o)){ currentNode.rightChild.parent.availableToAddRightChildren = false; currentNode.rightChild = null; return true; } queue.offer(currentNode.rightChild); } } return false; }

Djole

Level 41 , Belgrade, Serbia

7 July 2019, 22:11

it works The list size is 15 The expected parent is 3. The actual parent is 3 The expected parent is null. The actual parent is null The expected parent is null. The actual parent is null The expected parent is 9. The actual parent is 9 Expected: true. Actual: true The expected parent is 1. The actual parent is 1 Process finished with exit code 0 but i would like to see more elegant way in implementing add, cause i am not happy with my solution

Djole

Level 41 , Belgrade, Serbia

7 July 2019, 22:12

i forgot void checkChildren() { if (leftChild != null) { availableToAddLeftChildren = false; } if (rightChild != null) { availableToAddRightChildren = false; } }

Djole

Level 41 , Belgrade, Serbia

8 July 2019, 10:50

you can ignore immutable list. temp list is enough there, i was just experimenting with unmodifiable list there fogrot to erase it after i was done.