1

I am stuck on one of my university labs about Trees and hoping someone can help me figure this out. They have asked us to write a method called maxDegree() which returns the largest number of children of any node. I am struggling to figure out how to implement this, if anyone could look at my current method and point me in the right direction that would be great!

Diagram of example tree - https://i.sstatic.net/XZ3bl.jpg

package week10;

import java.util.*;

/**
 * Skeleton of the recursive implementation of a general tree.
 * 
 * @author Michael Albert
 * @param <T> The type of values stored in the tree.
 */
public class Tree<T> {

    private T rootValue;
    private List<Tree<T>> children;

    public Tree(T rootValue, List<Tree<T>> children) {
        this.rootValue = rootValue;
        this.children = children;
    }

    public Tree(T rootValue) {
        this(rootValue, new ArrayList<Tree<T>>());
    }

    public int size() {
        int count = 1;
        for (Tree<T> child : children) {
            count += child.size();
        }
        return count;
    }

    //METHOD I AM STUCK ON
    public int maxDegree() {
        int largestNode = 0;
        for (Tree<T> child : children) {
            child.maxDegree();
            if (child.size() > largestNode) {
                System.out.println("test" + children.size());
                largestNode = child.size();
            }
        }
        return largestNode;
    }

    public void add(Tree<T> child) {
        children.add(child);
    }

    public Tree<T> find(T value) {
        if (rootValue.equals(value)) {
            return this;
        }
        for (Tree<T> child : children) {
            Tree<T> match = child.find(value);
            if (match != null) {
                return match;
            }
        }
        return null;
    }

    public List<T> postOrder() {
        // implement this method
        return new ArrayList<T>();
    }

    public String toString() {
        if (children.isEmpty()) {
            return rootValue.toString();
        }
        return rootValue.toString() + ' ' + children.toString();
    }

    public String toIndentedString() {
        // implement this method
        return "Not implemented yet!";
    }

    /** A helper method for testing (used by main).  Searches tree for
     *  the given target and adds white space separated children to
     *  the tree matching target if there is one.
     *
     * @param target the root value to seach for.
     * @param children a white space separated list of children to add
     * to the tree whose value matches target.
     */
    private static void addChildren(String target, String children) {
        Tree<String> parent = tree.find(target);
        if (parent != null) {
            for (String child : children.split(" ")) {
                parent.add(new Tree<>(child));
            }
        }
    }

    /** A tree instance used for testing. */
    private static Tree<String> tree;

    /**
     * Entry point of the program (used for testing).
     *
     * @param args command line arguments are not used.
     */
    public static void main(String[] args) {
        System.out.println("Creating tree\n-------------");
        tree = new Tree<>("food");
        System.out.print(tree + "\nsize: " + tree.size());
        System.out.println(", max degree: " + tree.maxDegree());
        System.out.println("\nAdding children\n----------------");
        addChildren("food", "meat fruit vegetable");
        System.out.print(tree + "\nsize: " + tree.size());
        System.out.println(", max degree: " + tree.maxDegree());
        System.out.println("\nAdding deeper children\n----------------------");
        addChildren("meat", "chicken beef fish");
        addChildren("fish", "salmon cod tuna shark");
        addChildren("vegetable", "cabbage");
        System.out.print(tree + "\nsize: " + tree.size());
        System.out.println(", max degree: " + tree.maxDegree());
        System.out.println("\nPostorder\n---------");
        System.out.println(tree.postOrder());
        System.out.println("\nIndented string\n---------------");
        System.out.print(tree.toIndentedString());
    }

}
4
  • In your example tree, would the largest be 4 because the fish node has the most children of 4. Is that what you are asking? Commented May 9, 2017 at 4:09
  • Yes that is it, the largest would be 4 Commented May 9, 2017 at 4:12
  • I have added a link to a picture of the diagram Commented May 9, 2017 at 4:20
  • The size() function returns the count of all the children of that node, but for the maxDegree() you only need the count of the immediate children Commented May 9, 2017 at 4:32

1 Answer 1

1

This will work:

public int maxDegree()
{
    // Get the number of immediate children
    int numChildren = this.children.size();

    // Find the max of all children
    int maxOfChildren = 0;
    for (Tree<T> child : children)
    {
        maxOfChildren = Math.max(maxOfChildren, child.maxDegree());
    }

    // return the greater of immediate child or max of children
    return Math.max(numChildren, maxOfChildren);
}

Explanation for your example Tree

  1. Max degree is called on the food node (it has 3 immediate children)
  2. We loop through all children of food (meat, fruit, vegetable, )
  3. Max degree is called on the meat node (it has 3 immediate children)
  4. We loop through all children of meat (chicken, beef, fish, )
  5. Max degree is called on the chicken node (it has 0 immediate children)
  6. Max degree of chicken is 0
  7. Max degree is called on the beef node (it has 0 immediate children)
  8. Max degree of beef is 0
  9. Max degree is called on the fish node (it has 4 immediate children)
  10. We loop through all children of fish (salmon, cod, tuna, shark, )
  11. Max degree is called on the salmon node (it has 0 immediate children)
  12. Max degree of salmon is 0
  13. Max degree is called on the cod node (it has 0 immediate children)
  14. Max degree of cod is 0
  15. Max degree is called on the tuna node (it has 0 immediate children)
  16. Max degree of tuna is 0
  17. Max degree is called on the shark node (it has 0 immediate children)
  18. Max degree of shark is 0
  19. Max degree of all children of fish is 0
  20. Max degree of fish is 4
  21. Max degree of all children of meat is 4
  22. Max degree of meat is 4
  23. Max degree is called on the fruit node (it has 0 immediate children)
  24. Max degree of fruit is 0
  25. Max degree is called on the vegetable node (it has 1 immediate children)
  26. We loop through all children of vegetable (cabbage, )
  27. Max degree is called on the cabbage node (it has 0 immediate children)
  28. Max degree of cabbage is 0
  29. Max degree of all children of vegetable is 0
  30. Max degree of vegetable is 1
  31. Max degree of all children of food is 4
  32. Max degree of food is 4
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.