Skip to content

Method to get all the branches of a tree

I have an object from this Class:

public class Person{
    private String name;
    private List<Person> children;
}

And I would like to write the JAVA method: private List<List> extractNames(Person ancestor) which gives back all the names of each branch of the tree:

enter image description here

Do you have an idea, how I could do it ?

Answer

Update: Removed the dependency to lombok

The relevant algorithm part is in the method extractNamesAlternative in the class PersonGetNamesTest. The rest of the code is just some sugar so it can be run with junit. If you don’t know how to use junit, copy the method extractNamesAlternative to your own class.

Person.java

import java.util.ArrayList;
import java.util.List;

public class Person {

    private String name;
    private List<Person> children = new ArrayList<>();

    Person(String name, List<Person> children){
        this.name = name;
        this.children = children;
    }
    
    Person(String name){
        this.name = name;
    }

    public String getName(){
        return name;
    }

    public List<Person> getChildren(){
        return children;
    }
}

ExtractNamesTest.java

import org.assertj.core.util.Lists;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class ExtractNamesTest {

    @Test
    void testPersonGetNamesTest() {
        Person personD = new Person("D");
        Person personE = new Person("E");
        Person personF = new Person("F");

        Person personB = new Person("B", Arrays.asList(personD, personE, personF));
        Person personG = new Person("G");
        Person personH = new Person("H");

        Person personC = new Person("C", Arrays.asList(personG, personH));
        
        Person personA = new Person("A", Arrays.asList(personB, personC));


        List<String> namesAlternative = extractNamesAlternative(personA, new ArrayList<>(), new ArrayList<>());
        assertEquals(Lists.list(
                "ABD", "ABE", "ABF", "ACG", "ACH"),
                namesAlternative);
    }

    private List<String> extractNamesAlternative(Person ancestor, List<String> names, List<Person> allAncestors) {
        allAncestors.add(ancestor);
        if (ancestor.getChildren().isEmpty()) {
            names.add(allAncestors.stream().map(Person::getName).collect(Collectors.joining()));
            return names;
        } else {
            for (Person p : ancestor.getChildren()) {
                extractNamesAlternative(p, names, new ArrayList<Person>(allAncestors));
            }
        }
        return names;
    }
}