How can I recursively traverse a graphql document in java and find the deepest level it reaches

Question

My goal is to traverse a graphql Java document object and return the max depth.

Example: Depth 0

{
   name 
}

Example: Depth 1

{
   viewer{
     viewerId
   }
}

Example: Depth 2

{
   viewer{
     albums{
       albumId
     }
   }
}

Example: Depth 2. As you can see both albums/songs are under same parent 'viewer'

{
   viewer{
     albums{
       albumId
     }
     songs{
        songId
     }
   }
}

Example: Depth 3

{
   viewer{
     albums{
       tracks{
          trackId
       }
     }
   }
}

I have written the base code to traverse it but my code doesn't work for the 2nd version of depth = 2. It returns depth = 3 instead of 2. The reason is because it's counting twice under the same parent. Essentially the logic is this: depth = depth + 1 whenever a field has children.

import graphql.language.Document;
import graphql.language.Node;
import graphql.language.OperationDefinition;

public int checkDepthLimit(String query) {
    Document document;
    try {
        document = documentParser.parseDocument(query);
    } catch (Exception e) {}

    Optional<Node> queryNode = document.getChildren().stream()
            .filter(n -> (n.getClass() == OperationDefinition.class))
            .findFirst();

    return checkDepthLimit(queryNode.get());

}

---

private int checkDepthLimit(Node queryNode) {

    int depth = 0;
    String nodeType = queryNode.getClass().getSimpleName().toUpperCase();

    if (nodeType.equals("FIELD")) {
        if (!queryNode.getChildren().isEmpty()) {
            depth += 1;
        }
    }

    List<Node> nodeChildren = queryNode.getChildren();
    for (int i = 0; i < nodeChildren.size(); i++) {
        depth += checkDepthLimit(nodeChildren.get(i));
    }
    return depth;

}

---

String query = "{
       viewer{
           viewerId
       }"
QueryComplexity c = new QueryComplexity();
int depth = c.checkDepthLimit(query);

I am stuck and would very much appreciate if someone with deeper knowledge of recursion would be able to help me.

Answer 1

The error is where you iterate the children. As you already recognized ("counting twice"), you add the depth of every child to the current depth, but you should only add the deepest one.

This does the trick:

    List<Node> nodeChildren = queryNode.getChildren();
    int maxChildDepth = 0;
    for (int i = 0; i < nodeChildren.size(); i++) {
        final int currentChildDepth = checkDepthLimit(nodeChildren.get(i));
        maxChildDepth = Math.max(maxChildDepth, currentChildDepth);
    }
    depth += maxChildDepth;
    return depth;