CodeGym/Help with Java Tasks/I need a hint

Level 50

Kraków

24.08.2023
340views
9comments

I need a hint

Question about the task

Resolved

Ok my code looks like that. I don't know exactly what Validator want from me. I don't know whether I can use linkedLists / arrayLists ? // line 13 For start I implemented add() size() and getParrent() method and I get 3 red from validator, then I implemented remove() because I thought maybe I must do it too. I need a hint what's wrong, what I can do here and what I can't. Now program correctly adding and removing elements from list (I think so). But maybe your eyes help me catch some mistakes!

Every tree starts with a root, so don't forget to add an Entry<String> field called root with the default access modifier to the CustomTree class.

Initialize it in the CustomTree constructor. It's name (elementName) isn't important.

Now that we've built the tree's foundation, it's time for you to do a little work on your own.

Recall what our tree should look like.

The nodes of the tree should be like those in the picture:

Now we need to write methods that will allow us to create and perform operations on that tree structure.

You need to:
1) override the add(String s) method, which adds tree nodes; it takes a node name as an argument (elementName) and searches left to right for a place to insert it.
2) override the size() method so it returns the current number of nodes in the tree.
3) implement the getParent(String s) method so it returns the name of the parent of the tree node passed as an argument.

You can create methods and fields not listed in the task, if necessary.

Requirements:

There must be an Entry field called root in the CustomTree.Entry class.
Override the add(String s) and size() methods in the CustomTree class.
After using the add method to add N nodes to the tree, the size method must return N.
The getParent method must return the name of the parent of any node in the tree.

package com.codegym.task.task20.task2028; import java.util.List; public class Solution { public static void main(String[] args) { CustomTree list = new CustomTree(new CustomTree.Entry<>("0")); 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 " + list.getParent("8")); System.out.println("The expected parent is 9. The actual parent is " + list.getParent("20")); System.out.println("The expected parent is 7. The actual parent is " + list.getParent("16")); System.out.println("The expected parent is 14. The actual parent is " + list.getParent("30")); System.out.println("The expected parent is 9. The actual parent is " + list.getParent("20")); list.remove("3"); for (CustomTree.Entry<String> s :list.getList()) { System.out.println(s); } } }

Comments (9)

Popular
New
Old

You must be signed in to leave a comment

Guadalupe Gagnon

Level 37 , Tampa, United States

24 August 2023, 15:44

solution

I think you modified the CustomTree constructor. It should be a no argument constructor. For the adding a new element a very easy algorithm is to start by creating a first in first out queue. Add the root. Then start a loop that takes the next item in the queue out and: - checks if its left node is available and adds the new element if true or else adds that node to the queue - checks if its right node is available and adds the new element if true or else adds that node to the queue (break the loop when the correct spot is found) - loop restarts so something like this:

Queue<String> queue = new LinkedList<>();
queue.offer(root);
Entry<String> current;
while(true){
   current = queue.poll(); // get next

   // check if left is available, add new entity if true or put left node in queue
   if(current.isLeftAv()){
      current.addToLeft(theNewEntry);
      break;
   } else queue.offer(current.getLet());

   // check if right is available, add new entity if true or put right node in queue
   if(current.isRightAv()){
      current.addToRight(theNewEntry);
      break;
   } else queue.offer(current.getRight());
}

This is a nice clean algorithm for searching a tree from left to right for the first available spot. You need to check the boolean flag for availability and not if the left or right node is null. This is because when you remove a node your code should not fill in the newly empty space.

Thomas

Level 41 , Bayreuth, Germany

24 August 2023, 15:44

solution

Why a list? You do not need it. Having the root element (line 12) is the tree. You look at the root (I ignore the isAvailableToAddChildren, availableToAddLeftChildren, availableToAddRightChildren). The root is of type Entry and has a parent, a left and right child (the roots parent is null). If a child is not null, then you look at it. It again has parent (the previous Entry you looked at, left and right nodes). That way you can iterate over the entire tree. There are different ways to iterate over the trees (post order, pre order, level order, in order - you can google them if it is from interest for you). Here it's level order and that's easily implemented using a queue. Put the root into the queue. 1 while the loop has more elements 2 get and remove the entry, 3 look at it and output the value (eg for the first root element 1). If it has children : 4 add these to the queue now back to 1, get the first child and print its value (2), if it has children -> to the queue next element is 3, print it and add it's children to the queue... I have forgotten if you really need to mess with the availableToAddLeftChildren here or if it is for another sub task

Guadalupe Gagnon

Level 37 , Tampa, United States

24 August 2023, 15:46

=P you commented slightly before me

Thomas

Level 41 , Bayreuth, Germany

24 August 2023, 15:49

Yah, but you offered the written code ;)

matemate123

Level 50 , Kraków, Poland

24 August 2023, 18:13

My two mentors, always you can count on them! I'm getting to work, I think I get it. I'm not using Guadalupe code, must write myself

matemate123

Level 50 , Kraków, Poland

25 August 2023, 10:47

After all I had to use help a "little" help from Guadalupe code to implement this method :D I tried for some time to do this task without any queue. But I think is possible only with some mathematical equation which help us iterate, and where branch to go. If someone have solution without queue, I want to see it! Nonetheless queue is ideal solution here and I must spent a little time to correctly understand the process which occurs. Thanks for help Guadalupe and Thomas. You're the best!

Thomas

Level 41 , Bayreuth, Germany

26 August 2023, 06:51

useful

This task is meant to be solved using a queue. That is due to the fact a condition is to add the elements from left to right. This is not always the best strategy but one that is easy to understand. Eg. when you have a search- of AVL-tree, then you add the elements in a sorted way and not one by one from left to right. Depending on your tree some ways may be faster to access relevant parts of that very tree. The queue way is iterating one by one... that's slow if you want to reach the leaves, the end of the tree. Here you use one of the previously mentioned other strategies like post order (in order or pre order). They all work pretty much the same (recursive). The difference is, when the algorithm is doing some action. Imagine a basic tree and we add (using the queue method the numbers 1 - 7)

           1
         /  \
       2     3
     /  \   /  \
    4   5  6    7

now we want to print the tree. level order top to bottom, left to right --> 1, 2, 3, 4, 5, 6, 7 but what if we first go left till there is no left anymore (4). If there's no further left and right, then we print and go back one step, go right and then, if there's no more children, we print (5) go back, it has no more children, print (2), here we visited all children so we just can go back to the root, the root has a right branch, now we visist that one, and then left all the way up (6)... and so on that's post order 4, 5, 2, 6, 7, 3, 1 If you print right away when stepping into the tree and not when you're on the way stepping backwards, then this is called pre order. Means you're at the root, print it 1, go left print, 2, go left 4, no more children, back 2 has a right child, go there and print 5... and so on 1, 2, 4, 5, 3, 6, 7 In order is doing the action between changing the branches. You go left.. all the way and before you check if there is a right child you print... 4, 2, 5, 1, 6, 3, 7

Thomas

Level 41 , Bayreuth, Germany

26 August 2023, 06:54

useful

Assuming the trees' class is named Tree here is some sample code to illustrate the bahaviour. It uses a functional interface. With that you can inject the behavior you want the edit method do, like outputting comma separated tree.preOrder(e -> System.out.print(e.value + ", ")); Important is just where the action is happening before stepping into the branches (pre), before returning (post) or when switching branches (in).

public interface Editor<T> {
    void edit(Tree<T> b);
}

public void preOrder(Editor<T> editor) {
    editor.edit(this);
    if (this.left != null)
        left.preOrder(editor);
    if (this.right != null)
        right.preOrder(editor);
}

public void postOrder(Editor<T> editor) {
    if (this.left != null)
        left.postOrder(editor);
    if (this.right != null)
        right.postOrder(editor);
    editor.edit(this);
}

public void inOrder(Editor<T> editor) {
    if (this.left != null)
        left.inOrder(editor);
    editor.edit(this);
    if (this.right != null)
        right.inOrder(editor);
}

And sorry that I was to lazy to write code for the CG tree. That one is from my tries writing basic, search and AVL trees.

matemate123

Level 50 , Kraków, Poland

27 August 2023, 05:47

"This task is meant to be solved using a queue"

Yes I see it now how helpful and good solution that is. When I got this concept, rest of project was logic and pleasureable. Thanks for your time showing me these strategies, I'm sure it can help me in future tasks! I carefully analized what you show me, and when it'll be another task with tree I'll be back here to recall.