2
\$\begingroup\$

I'm a beginner and I wrote this (working) code for n-ary tree.

The specifics:

  • Each node is to be built with an integer value.
  • Each node has a variable number of children.
  • The nodes should have an add(Node n) method, that adds a child node.
  • The Tree should have a contains(int val) method, that returns a Boolean value (true if the number val is found in a node).
  • It should have an add(int... intArray) method, that attaches a branch to the root if the root corresponds to the first number in intArray. The other numbers in the intArray are to be added only if they don't already exist (each as a child of the number before it).
  • The Tree should have a remove(int r) method, that removes a the node with the value of r (if present) and attaches its children to its parent. If the node happens to be the root, then the first child of the root becomes the root.
import java.util.*;

public class NaryTree
{
    private Node root;

    static public class Node
    {
        private List<Node> children;
        private int value;

        public Node(List<Node> children, int value)
        {
            this.children = children;
            this.value = value;
        }

        public void add(Node n)
        {
            if (children == null) children = new ArrayList<>();
            children.add(n);
        }
    }

    public void add(int ... intArray) throws RootsNotEquals
    {
        if (root == null) root = new Node(null, intArray[0]);
        if (root.value != intArray[0]) { throw new RootsNotEquals(); }
        else
        {
            if (intArray.length >= 1) { intArray = Arrays.copyOfRange(intArray, 1, intArray.length); }
            add(root, intArray);
        }
    }

    public void add(Node tempRoot, int ... intArray)
    {
        boolean present = false;
        int index = -1;

        for (int i = 0; i < intArray.length; i++)
        {
            if (tempRoot.children != null)
            {
                for (int j = 0; j < tempRoot.children.size()-1; j++)
                {
                    if (tempRoot.children.get(j).value == intArray[0]) present = true;
                }
            }
            if (!present) { tempRoot.add(new Node(null, intArray[0])); }
            for (Node f : tempRoot.children)
            {
                index++;
                if (f.value == intArray[0])
                {
                    if (index <= tempRoot.children.size()-1) tempRoot = tempRoot.children.get(index);
                    if (intArray.length >= 1) intArray = Arrays.copyOfRange(intArray, 1, intArray.length);
                    add(tempRoot, intArray);
                    break;
                }
            }
            break;
        }
    }

    public void remove(int r) throws NodeNotFound
    {
        if (!contains(r)) throw new NodeNotFound();
        if (root.value == r)
        {
            for (int i = 1; i < root.children.size(); i++)
            {
                root.children.get(0).children.add(root.children.get(i));
            }
            root = root.children.get(0);
        }
        else { remove(root, r); }
    }

    public void remove(Node tempRoot, int r)
    {
        if (tempRoot.children != null)
        {
            for (int i = 0; i < tempRoot.children.size(); i++)
            {
                if (tempRoot.children.get(i).value == r)
                {
                    for (Node n : tempRoot.children.get(i).children) tempRoot.children.add(n);
                    tempRoot.children.remove(i);
                }
                else
                {
                    tempRoot = tempRoot.children.get(i);
                    remove(tempRoot, r);
                    break;
                }
            }
        }
    }

    public boolean contains(int val) { return contains(root, val); }

    private boolean contains(Node n, int val)
    {
        boolean found = false;
        if (n == null) return found;
        if (n.value == val) found = true;
        else if (n.children != null) for (Node f : n.children) { return contains(f, val); }
        return found;
    }

    public void print()
    {
        System.out.println("The root is "+root.value+".");
        for (Node n : root.children)
        {
            System.out.println(n.value+" is a child of the root.");
            printChildren(n);
        }
    }

    public void printChildren(Node n)
    {
        if (n.children != null)
        {
            for (Node child : n.children)
            {
                System.out.println("Node "+n.value+" has node "+child.value+" as a child.");
                printChildren(child);
            }
        }
    }

    public static void main(String[] args) throws RootsNotEquals, NodeNotFound
    {
        NaryTree poplar = new NaryTree();

        poplar.add( new int[] { 1, 2, 5 });
        poplar.add( new int[] { 1, 4, 0, 0 } );
        poplar.add( new int[] { 1, 3, 6 });
        poplar.add( new int[] { 1, 2, 7 });
        poplar.print();
    }
}
\$\endgroup\$
  • \$\begingroup\$ I wrote up a review, but contains doesn't seem right, so I left it off. Have you tried adding poplar.remove(3) just before you print? Does it remove or not? \$\endgroup\$ – mdfst13 Dec 20 '18 at 16:39
  • \$\begingroup\$ Yes, I've tested it and it works as intended. \$\endgroup\$ – Ary Dec 21 '18 at 7:45
2
\$\begingroup\$
        private List<Node> children;

Your logic would become a lot easier if you changed this to

        private List<Node> children = new ArrayList<>();

A large number of null checks would disappear. This would increase the amount of memory used, but it is unclear how much of a difference that would make.

        public Node(List<Node> children, int value)

This seems like a solution in search of a problem. Your caller should not need to know about Node at all, so this always be called with null.

        public Node(int value)

This way, you support the natural path. The caller only needs to know that the tree holds integers. It does not need to know anything about how it holds them.

        if (root.value != intArray[0]) { throw new RootsNotEquals(); }
        else

You don't need an else here. The throw ends the current method.

If you are going to put brackets around your single statement in control structures, you should do so consistently. You sometimes use the more common single statement form and sometimes this one. You should pick one.

Incidentally, the java standard is to write control structures like

        if (root.value != intArray[0]) {
            throw new RootsNotEquals();
        }

If you write them like this every time, you will tend to use less vertical space than you do with your mixture of all on the same line and all on separate lines.

            if (intArray.length >= 1) { intArray = Arrays.copyOfRange(intArray, 1, intArray.length); }
            add(root, intArray);

This seems silly. You call add even if it's unnecessary despite checking the right condition immediately before it. Why not

        if (intArray.length >= 1) {
            intArray = Arrays.copyOfRange(intArray, 1, intArray.length);
            add(root, intArray);
        }

This will save you a method call that will end up being a no-op.

You also might consider doing the length check at the beginning of the method. Because if the length is 0, then intArray[0] will throw an exception. So you'd never reach the code that does the check.

I also think that this method's behavior is rather silly. In order to add multiple, you need to pass in the root value. As a password? In the real world, if you received a requirement like this, it would be natural to push back and ask for the requirement to be removed. Perhaps it exists here for didactic purpose.

        for (int i = 0; i < intArray.length; i++)

Why? At the end of the iteration, you have

            break;

So this only ever does one iteration. Just take it out. It does not actually accomplish anything and you never use i.

                    if (index <= tempRoot.children.size()-1) tempRoot = tempRoot.children.get(index);

This will always be true, so it could be just

                tempRoot = f;

And you could get rid of index entirely.

                    if (intArray.length >= 1) intArray = Arrays.copyOfRange(intArray, 1, intArray.length);

Again, this will always be true.

                    add(tempRoot, intArray);

This could be

                add(f, Arrays.copyOfRange(intArray, 1, intArray.length));

Note that this creates a new array each time. You might be better off passing an index variable and changing your [0] to [index].

In remove(int), you have

        if (!contains(r)) throw new NodeNotFound();

Consider implementing a findParentOf(int) instead. Because this essentially searches the tree, finds the element that you want, forgets the location of the element, and returns true or false. Then you go off and find the element again. You'd use it like

        Node parent = findParentOf(r);
        if (r == null) {
            throw new NodeNotFound();
        }

And of course, you'd do this after checking if it's the root value (don't forget to check for null first).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.