The intended design of this tree is not clear from the instructions

Question about the task

Resolved

In the example graphic, I understand that each Entry has a right and left "child" Entry, or at least the potential to have them. I also understand that if you remove an Entry (such as in the example list.remove("3")) it removes all the child entries as well. But I do not understand the placement of the example list.add("16"). Why does it branch off of 9? Isn't the left child for entry 1 available again at this point? If the slots for entry children do not become available after they are emptied, would this imply that removing entry 1 and entry 2 would leave a root entry 0 that cannot have anything else added to it? Also, what happens if, instead of list.add("16") I used list.add("20")? Would it still go under the left child of entry 9, or would it place it where it would be if all the in-between entries had been placed first?

Comments (3)

Popular
New
Old

You must be signed in to leave a comment

Guadalupe Gagnon

Level 37 , Tampa, United States

16 August 2022, 14:25

This task is asking you to implement a non-standard binary tree. The last task had you set up two boolean class fields that flag if the left and right nodes were available to have a child added. Removing an element does not set that variable to true. This means that in the example "1" already had a left element (the third element which was removed) and its boolean flag for if the left node can have a child would be false. When an element is added the code should find the left most open node to add the element at the bottom level. The left node of the "9" element in the graph would be the left most open node in that tree as the level that "9" is on is all filled up. Another example, in the graph, imagine that instead of removing "3" that it instead removed "4". If you added "16" then that would be added as the right child to "7" (the left most open node at the bottom level). "17" and "18" would be children of "8". Then if you added "19" that would be the left child of "11" because that would be the left most open node at the current bottom level. One last example, lets say in step one we added 14 elements, then removed element "1". If we added another element, "15", that would go to the left node of "11" because that would be the left most open node at the bottom level.

Guadalupe Gagnon

Level 37 , Tampa, United States

16 August 2022, 14:39

useful

A hint: a simple algorithm is to use a FIFO queue.

// create queue
// Start by adding the root.
// in loop, if queue has more elements {
   // 2) get the next element
   // 3) check if element can have children. If yes then add the new element and break
   // 4) if not add the left element and then add the right element (if they are present) to queue
}

Justin Smith

Level 41 , Greenfield, USA, United States

17 August 2022, 01:17

Yeah, I had initially started with a recursive method, it's a terrible idea due to the order it needs to search with. I can't even make recursion work here. Queue it is.