Java Tree Search

Question

I try to solve to problem with tree traversing. I feel I very close to solve it but I need more clue.

So I have two interfaces:

public interface Department {

    String getName();

    String getType();
}

public interface Company extends Department {
    List<Department> getDepartments();
}

So this creates Tree structure.

I want to find Department List by type.

I implemented finding a single element already.

public class Concern {
    private List<Department> getDepartments;


    public Optional<Department> findDepartmentByName(String name) {
        return findDepartmentByPredicate(department -> department.getName().equals(name)).findFirst();
    }

    public List<Department> findDeparmentByType(String type) {
        return findDepartmentByPredicate(department -> deparment.getType().equals(type))
                .toList();
    }

    private Stream<Department> findDepartmentByPredicate(Predicate<Department> predicate) {
        return department.stream()
                .map(department -> department.getMatchingDepartment(predicate))
                .filter(Optional::isPresent)
                .map(Optional::get);
    }

}

I trying using this with one function.

public interface Department {
   ....

    default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
        if (predicate.test(this)) {
            return Optional.of(this);
        }
        return Optional.empty();
    }
}

And this is a part where I don't how to do this.

I try to call getMatchingDepartment on every list element but it don't traverse all child elements.

public interface Comapny extends Deparment {

    default Optional<Department> getMatchingDepartment(Predicate<Department> predicate) {
        return getDepartments().stream()
                .map(department -> department.getMatchingDepartment(predicate))
                .filter(Optional::isPresent)
                .map(Optional::get)
                .findFirst();

    }


}

Is it possible to do this that way ? I need to use recursion somehow?

Is a company a department?

Cheng Thao
– Cheng Thao

2022-11-15 14:05:30 +00:00
Commented Nov 15, 2022 at 14:05 — Cheng Thao
– Cheng Thao, Commented Nov 15, 2022 at 14:05
In this exercise yes.

wesky77
– wesky77

2022-11-15 14:12:01 +00:00
Commented Nov 15, 2022 at 14:12 — wesky77
– wesky77, Commented Nov 15, 2022 at 14:12

Thomas Behr · Accepted Answer · 2022-11-15 11:23:22Z

You can use recursion

public List<Department> findDepartmentByType( String type ) {
  ArrayList<Department> result = new ArrayList<>();
  findDepartmentByTypeImpl(type, getDepartments(), result);
  return result;
}

private void findDepartmentByTypeImpl( String type, List<Department> departments, List<Department> result ) {
  for (Department current : departments) {
    if (type.equals(current.getType())) {
      result.add(current);
    }
    if (current instanceof Company) {
      findDepartmentByTypeImpl(type, ((Company) current).getDepartments(), result);
    }
  }
}

but it is also possible to use an iterative approach

public List<Department> findDepartmentByType( String type ) {
  ArrayList<Department> result = new ArrayList<>();

  ArrayList<Department> stack = new ArrayList<>();
  stack.addAll(getDepartments());
  while (!stack.isEmpty()) {
    Department current = stack.remove(stack.size() - 1);
    if (type.equals(current.getType())) {
      result.add(current);
    }
    if (current instanceof Company) {
      stack.addAll(((Company) current).getDepartments());
    }
  }

  return result;
}

(Not tested, use at your own risk.)

Collectives™ on Stack Overflow

Java Tree Search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related