Unable to Fully Recurse Tree Hierarchy Using Java

Question

Have created a Spring Boot Microservice which issues an HTTP GET to pull data (per Node) from a MySQL Database which data setup inside a single table based on Adjacency List Tree.

Am able to get a node's children at a specific level but needed to be able also to see all the children (even if it entails a different REST call and service method).

Am using Java 1.8, Spring Boot 1.5.6.RELEASE, JPA & MySQL 5 in my tech stack.

pom.xml:

<parent>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-parent</artifactId>
    <version>1.5.6.RELEASE</version>
</parent>

<properties>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
    <java.version>1.8</java.version>
</properties>

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>

    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-test</artifactId>
        <scope>test</scope>
    </dependency>

    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-jpa</artifactId>
    </dependency>

    <dependency>
        <groupId>javax.xml.bind</groupId>
        <artifactId>jaxb-api</artifactId>
        <version>2.3.0</version>
    </dependency>

    <dependency>
        <groupId>mysql</groupId>
        <artifactId>mysql-connector-java</artifactId>
        <scope>runtime</scope>
    </dependency>
</dependencies>

Node.java (POJO):

@Entity
public class Node {

    @Id
    @GeneratedValue(strategy=GenerationType.IDENTITY)
    private Long id;

    @NotNull
    private String name;

    @Column(name = "parent_id")
    private Long parentId;

    // Getters & Setters Omitted for Brevity 
}

NodeRepository:

@Repository
public interface NodeRepository extends JpaRepository<Node, Long> {

    @Query(value = "SELECT * FROM NODE WHERE parent_id = ?", nativeQuery = true)
    List<Node> findNodesByParentId(Long parentId);

    @Query(value = "SELECT * FROM NODE WHERE name = ?", nativeQuery = true)
    Node findByName(String name);
}

MyService:

public interface MyService {
    List<Node> getHierarchyPerNode(Node node);
    void removeNode(String node);
}

MyServiceImpl:

@Service
public class MyServiceImpl implements MyService {

   @Autowired
   NodeRepository repository;

   @Override
   public List<Node> getHierarchyPerNode(Node node) {
        List<Node> nodes = new ArrayList<>();
        List<Node> children = new ArrayList<>();
        if (node != null) {
            Node aNode = repository.findByName(node.getName());
            nodes.add(aNode);
            Long parentId = aNode.getId();
            children = repository.findNodesByParentId(parentId);

            // Was trying this as recursion but kept throwing an NullPointerException.
            // for (Node child : children) {
            //      return getHierarchyPerNode(child);
            //  }
        }
        if (!children.isEmpty()) {
            return children;
        } 
        else { 
            return nodes;
        }
    }
}

RestController:

@RestController
public class RestController {

    private HttpHeaders headers = null;

    @Autowired
    MyService myService;

    public RestController() {
        headers = new HttpHeaders();
        headers.add("Content-Type", "application/json");
    }

    @RequestMapping(
        value = {"/api/nodes"}, 
        method = RequestMethod.GET, 
        produces = "APPLICATION/JSON"
    )
    public ResponseEntity<Object> getHierarchyPerNode(Node node) {
        if (null == node) {
            return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
        }
        List<Node> nodes = myService.getHierarchyPerNode(node);

        if (null == nodes) {
            return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
        }

        return new ResponseEntity<Object>(nodes, headers, HttpStatus.OK);
    }
}

DatabasePopulator (use this to populate the database during Spring Boot startup):

@Component
public class DatabasePopulator implements ApplicationListener<ContextRefreshedEvent> {

    private final NodeRepository repository;

    public DatabasePopulator(NodeRepository repository) {
        this.repository = repository;
    }

    @Override
    public void onApplicationEvent(ContextRefreshedEvent event) {
        Node root = new Node();
        root.setName("Store");
        root.setParentId(null);
        repository.save(root);

        // Populate Books Node (along with children)
        Node books = new Node();
        books.setName("Books");
        books.setParentId(root.getId());
        repository.save(books);

        Node horror = new Node();
        horror.setName("Horror");
        horror.setParentId(books.getId());
        repository.save(horror);

        Node romance = new Node();
        romance.setName("Romance");
        romance.setParentId(books.getId());
        repository.save(romance);

        Node fantasy = new Node();
        fantasy.setName("Fantasy");
        fantasy.setParentId(books.getId());
        repository.save(fantasy);

        // Populate Coffee Node (along with children)
        Node coffee = new Node();
        coffee.setName("Coffee");
        coffee.setParentId(root.getId());
        repository.save(coffee);

        Node mocha = new Node();
        mocha.setName("Mocha");
        mocha.setParentId(coffee.getId());
        repository.save(mocha);

        Node latte = new Node();
        latte.setName("Latte");
        latte.setParentId(coffee.getId());
        repository.save(latte);

        // Populate show espresso as a child underneath the Latte node.
        Node espresso = new Node();
        espresso.setName("Espresso");
        espresso.setParentId(latte.getId());
        repository.save(espresso);
    }
}

Clearly, the data populated represents this tree, inside the database:

Store
|______ Books
        |
        |______Horror
        |
        |______Romance
        |
        |______Fantasy

 |______Coffee
        |
        |______Mocha
        |
        |______Latte
               |
               |_____Espresso

Observation(s) / Question(s):

Through my RestController, I can obtain the first level of records by calling this REST Endpoint:

http://localhost:8080/myapp/api/nodes?name=Products

However, it ONLY gives me the first level (not the child nodes underneath Books & Coffee and Latte):

[
  {
    "id": 2,
    "name": "Books",
    "parentId": 1
  },
  {
    "id": 6,
    "name": "Coffee",
    "parentId": 1
  }
]

Instead of also listing Horror, Romance, Fantasy under Books and Mocha, Latte under Coffee (along with Espresso under Latte)

Now, if I use the parentNode (e.g. Books), it does show the children (but only the first level):

http://localhost:8080/myapp/api/nodes?name=Books

JSON Response Payload:

[
  {
    "id": 3,
    "name": "Horror",
    "parentId": 2
  },
  {
    "id": 4,
    "name": "Romance",
    "parentId": 2
  },
  {
    "id": 5,
    "name": "Fantasy",
    "parentId": 2
  }
]   

When trying to list all children of Coffee:

http://localhost:8080/myapp/api/nodes?name=Coffee

JSON Response Payload:

[
  {
    "id": 7,
    "name": "Mocha",
    "parentId": 6
  },
  {
    "id": 8,
    "name": "Latte",
    "parentId": 6
  }
]

See, this one doesn't show Espresso, have to call the Latte as a parent to view explicitly:

http://localhost:8080/myapp/api/nodes?name=Latte

JSON Response Payload:

{
    "id": 9,
    "name": "Espresso",
    "parentId": 8
}

Am available to get the node at a specific children's level...

How can I use recursion to obtain all nodes at all levels (I know this will be a different REST GET call / REST Endpoint)?

Need to use recursion to get all sub-children / sub-levels but don't know how to do so for both cases (getting the child nodes and deletion of nodes).

Answer 1

Not sure why you do not take full advantage of JPA here, first of all on the entity level and later on, during querying where you use a native SQL instead of JPQL.

1) If you alter your entity as follows:

@Entity
public class Node {

    @Id
    @GeneratedValue(strategy=GenerationType.IDENTITY)
    private Long id;

    @NotNull
    private String name;

    @ManyToOne
    @JoinColumn(name = "parent_id")
    private Node parentNode;

    @OneToMany(mappedBy = "parentNode", 
               cascade = { CascadeType.DELETE, CascadeType.PERSIST} )
    private List<Node> children;
}

2) Then change your query just a little bit to make it JPQL compatible:

@Query(value = "select n from Node n inner join n.parentNode p where p.id = ?")
List<Node> findNodesByParentId(Long parentId);

Now, by default only the top level Node will be fetched here as by default @OneToMany relations are loaded lazily.

3) All you need to do at this point is alter a bit your recursive method to comply with the changes and get what you need:

Controller

@RequestMapping(
    value = {"/api/nodes"}, 
    method = RequestMethod.GET, 
    produces = "APPLICATION/JSON"
)
public ResponseEntity<Object> getNodeHierarchy(Node node) {
    if (null == node) {
        return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
    }
    List<Node> nodes = myService.getNodeHierarchy(node);

    if (null == nodes) {
        return new ResponseEntity<Object>(HttpStatus.NOT_FOUND);
    }

    return new ResponseEntity<Object>(nodes, headers, HttpStatus.OK);
}

Top level Node retrieval

 @Override
 @Transactional(readOnly = true)
 public List<Node> getNodeHierarchy(Node inNode){
    Node node = repository.findByName(inNode.getName());

    traverseNodeAndFetchChildren(node);

    return node.getChildren();
 }

Recursive traversal and fetching

public void traverseNodeAndFetchChildren(Node node) {
   int size = node.getChildren().size();

   if(size > 0){
      for(Node childNode: node.getChildren()){
         traverseNodeAndFetchChildren(childNode);
      }
   }       
}

node.getChildren().size() - this makes the Persistence Context to load lazily the @OneToMany dependencies.

4) It might be a good idea also to mark your service method as @Transactional(readOnly = true).

Answer 2

I will suggest you have to implements like maciej suggest.

there is a logical problem. instead of return getHierarchyPerNode(child);, you have to add in nodes.

public List<Node> getHierarchyPerNode(Node node) {
        List<Node> nodes = new ArrayList<>();
        List<Node> children = new ArrayList<>();
        if (node != null) {
            Node aNode = repository.findByName(node.getName());
            nodes.add(aNode);
            Long parentId = aNode.getId();
            children = repository.findNodesByParentId(parentId);

            // Was trying this as recursion but kept throwing an NullPointerException.
            if (children != null) {
                for (Node child : children) {
                    List<Node> childList = getHierarchyPerNode(child);
                    if (childList != null && !childList.isEmpty()) {
                        nodes.addAll(childList);
                    }
                }
            }
        }
        return nodes;
    }