Untitled

package comp1110.lab9;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Objects;

public class FamilyTree {
    /**
     * This function accepts an Individual <code>ancestor</code> representing
     * the root (common ancestor) of a family tree
     * and the name of a target individual to find within that family tree,
     * and returns a string representation of all the ancestors of that
     * individual, each separated by the string " born of ".
     * <p>
     * If target name matches the name of <code>ancestor</code>, then only
     * the target name is returned.
     * <p>
     * If the target name is not found within the family tree descended from
     * <code>ancestor</code>, then null is returned.
     * <p>
     * For example, given an Individual homer representing a person named
     * "Homer", who has children named "Lisa" and "Bart":
     * getAncestry(homer, "Lisa") returns "Lisa born of Homer";
     * getAncestry(homer, "Bart") returns "Bart born of Homer"; and
     * getAncestry(homer, "Homer") returns "Homer"; and
     * getAncestry(homer, "Barney") returns null
     * <p>
     * Note: each individual has only one parent in the family tree.
     *
     * @param ancestor   the root (common ancestor) of a family tree
     * @param targetName the name of an individual to find in the family tree
     * @return a String representing the ancestry of the individual named
     * <code>targetName</code>, or null if no such individual is found
     */
    public static String getAncestry(Individual ancestor, String targetName) {
        LinkedList<Individual> path = new LinkedList<>();
        boolean success = dfs(ancestor, targetName, path);
        if (!success) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int index = 0; index < path.size(); index++) {
            stringBuilder.append(path.get(index).name);
            if (index != path.size() - 1) {
                stringBuilder.append(" born of ");
            }
        }
        return stringBuilder.toString();
    }

    public static boolean dfs(Individual node, String targetName, LinkedList<Individual> path) {
        if (node == null) {
            return false;
        }
        path.push(node);
        if (node.name.equals(targetName)) {
            return true;
        }
        if (node.children != null) {
            for (var child : node.children) {
                if (dfs(child, targetName, path)) {
                    return true;
                }
            }
        }
        path.pop();
        return false;
    }

    /**
     * This class represents an individual with zero or more children.
     */
    static class Individual {
        public String name;
        /**
         * This individual's immediate descendants.
         * If this individual has no children, this field is null.
         */
        public Individual[] children;

        public Individual(String name, Individual[] children) {
            this.name = name;
            this.children = children;
        }
    }
}