CODEWITHSUNDEEP
javadata-structures
Thomas Gourouza
Thomas Gourouza

Reputation: 3

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 ?

Upvotes: 0

Views: 681

Answers (3)

Isma
Isma

Reputation: 168

Here I show how I've implemented the function:

private static void extractNames(Person ancestor, String branchName, List<String> listBranch){
    if(ancestor.getChildren().size()>0) {
        branchName = branchName + ancestor.getName() + ",";
        for(int i=0; i<ancestor.getChildren().size(); i++) {                
            extractNames(ancestor.getChildren().get(i), branchName, listBranch);                
        }
    }else {
        branchName = branchName + ancestor.getName();
        listBranch.add(branchName);
    }
}

And how it can be called from main:

public static void main(String[] args) {
    //Create persons
    Person pA = new Person("A");
    Person pB = new Person("B");
    Person pC = new Person("C");
    Person pD = new Person("D");
    Person pE = new Person("E");
    Person pF = new Person("F");
    Person pG = new Person("G");
    Person pH = new Person("H");
    
    //Assign children
    pA.addChildren(pB);
    pA.addChildren(pC);
    pB.addChildren(pD);
    pB.addChildren(pE);
    pB.addChildren(pF);
    pC.addChildren(pG);
    pC.addChildren(pH);
    
    List<String> branchList = new ArrayList<String>();
    //call      
    extractNames(pA, "", branchList);
    //print list
    for(int i=0;i<branchList.size();i++) {
        System.out.println(branchList.get(i));
    }
}

I hope this help you.

Upvotes: 0

Nik
Nik

Reputation: 202

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;
    }
}

Upvotes: 1

Swapstar
Swapstar

Reputation: 223

I am not very good with Java but here's the code for what you want to do in Python. Just convert the extractNames method to Java.

class Person:
    def __init__(self, name, children=[]):
        self.name = name
        self.children = children
        
personD = Person("D", [])
personE = Person("E", [])
personF = Person("F", [])

personB = Person("B", [personD,personE,personF])

personG = Person("G", [])
personH = Person("H", [])

personC = Person("C", [personG, personH])

personA = Person("A", [personB,personC])

def extractNames(personHead, branchStack):
    # Keep adding children to branch stack
    branchStack.append(personHead.name)
    if len(personHead.children) == 0:
        print(branchStack)
    for child in personHead.children:
        extractNames(child,branchStack)
        # After going till all children we will remove everything till the parent
        while (branchStack[-1] != personHead.name):
            branchStack.pop(-1)
    return
    
extractNames(personA,branchStack=[])

'''
Output: 
['A', 'B', 'D']
['A', 'B', 'E']
['A', 'B', 'F']
['A', 'C', 'G']
['A', 'C', 'H']
'''

Upvotes: 1

Related Questions