CODEWITHSUNDEEP
javarecursionred-black-tree
Christopher Jakob
Christopher Jakob

Reputation: 155

using recursion to add to a variable

below the code is using a private method to add to the variable count. Below that variable are conditionals which by my understanding, will not run until the recursion stack traces upword. Am I correct? My test is failing, and I am trying to see if it is because my code is wrong or I'm using recursion wrong.

public boolean containsRightRedEdge() {
    int count = 0;
    count += containsRightRedEdge(root);
    if(count > 0) return true;
    return false;
}

private int containsRightRedEdge(Node n) {
   if (n == null) return 0;
   if (isRed(n.right)) {
       return 1;
   }
   return containsRightRedEdge(n.left) + 0 + containsRightRedEdge(n.right);         
}

Upvotes: 0

Views: 111

Answers (2)

Sean Glover
Sean Glover

Reputation: 520

I would say you are using recursion pretty much correctly, but your choice of method names could be less confusing, and your logic could be simplified. I am not too familiar with the algorithm you're trying to implement, but you might try something like this:

public boolean containsRightRedEdge(Node root) {
   return getNumRightRedEdges(root) > 0;
}

private int getNumRightRedEdges(Node n) {
   if (n == null) return 0;
   if (isRedEdge(n)) return 1;

   return getNumRightRedEdges(n.left) + getNumRightRedEdges(n.right);
}

Generally a recursive method shouldn't have the same name as a non-recursive method. These method names communicate more clearly what each one does. Also your base cases might be wrong as you've got them written currently based on how I'm interpreting the algo should work. Of course, I don't know the code inside isRed() so I'm probably making wrong assumptions here.

Upvotes: 2

Christopher Jakob
Christopher Jakob

Reputation: 155

The code above in my question, is the correct way to use recursion in this instance. I just had a typo which is now resolved. Leaving the question for other peoples reference.

Upvotes: 0

Related Questions