detecting circular reference

Question

So in an interview, I was actually asked a simple question that goes like this, say that I have a nested JSON response, [a, b, c ,d [a, [b, [d, e], g], h]. I am asked to implement a class that basically can handle to store this data and a print method to do so, so here's what I have:

public class JSONode
{
   private String str;
   private JSONode nodes;

   public JSONode (String a, ArrayList<String> n)
   {
        str = a;
        nodes = n;
   }
}

public class JSONResp
{
  private ArrayList<JSONode> arr;

  public JSONResp ()
  {
    arr = new ArrayList<JSONode>();
  }

  public boolean checkCircular(JSONode temp)
  {
    for (int i = 0; i < arr.size(); i++)
    {
        if (arr.get(i).nodes == temp)
            return true;
    }
    return false;
  }

  public void add (JSONode nd)
  {
    if (!checkCircular(nd))
    arr.add(nd);
  }

  public void recurseJSONode(JSONode)
  {
      if (!JSONode.node)
           System.out.print(JSONode.str);
      else {
          System.out.print(JSONode.str);
          recurseJSONode(JSONode.node);
      }
  }

  public void print()
  {
    for (int i = 0; i < arr.size(); i++)
       recurseJSONode(arr.get(i));
  }

  public static void main (String[] args) {
      JSONResp x = new JSONResp();
      x.add(new JSONode("a", null);
      x.add(new JSONode("b", null);
  }

}

Now he said that there will circular references issues when I print, in other words I have list A = [a, b, c, D] and D = [q, t, y, A]. So he said I'd have to prevent from adding D by using the checkCircular above. I made an attempt. Also just a node I know my recurseJSONode isn't correct and so does the print, so looking for a suggestion to fix that as well.. I am just curious to this problem.

Answer 1

The reason your circular check isn't right is that you only look for an existing duplicate of JSONode under the one node you're trying to add it to. But A might be under B and B is under A, so each is unique within its parent's list.

Re: using a stack for tracking activity in a recursive function:

Set<SomeNodeType> stack = new HashSet<SomeNodeType>();
someRecursiveThing(rootNode, stack);

And then inside someRecursiveThing:

void someRecursiveThing(SomeNodeType under, Set<SomeNodeType> stack) {

    if (!stack.add(under)) {
        return;

    // continue happily, e.g. call self with child node,
    // passing down the stack

    SomeNodeType child = ...
    someRecursiveThing(child, stack)

    // finish by removing 'under' from the stack:
    stack.remove(under);
}

The advantage of HashSet is that add and remove typically run in constant time - the size of the tree is irrelevant.

For comparison:

Markus Lausberg's answer suggests doing a complete recursive search of the whole tree, which would be O(N) where N is the number of nodes in the tree, and as you are doing that check for every node it ends up being O(N^2). A tree of 10 nodes will do 100 node comparisons; a tree of 1000 nodes will do 1000,0000 node comparisons.

In kan's answer the check involves searching the parent chain, which will depend on the depth of the tree. For a perfectly lopsided tree (worst case) the depth will be the same as the number of nodes, giving O(N^2) again. For a balanced tree the depth will be ~log N, not much better (remember, the check has to be done for every node).

The effect of these differences depends on the comparison operation used to determine if two nodes are the same. If it is just a pointer comparison (i.e. you only care if they're the same object) and the tree is never very large, the overhead of HashSet may have a negative impact. Whereas if you need to compare two nodes in a more complex way, so each comparison is expensive, and the tree is large, then the optimised lookup of HashSet will become beneficial.