CODEWITHSUNDEEP
javarecursiontreebinary
brennan mcgowan
brennan mcgowan

Reputation: 125

How is recursion working within this method?

I am writing a method to find if a binary tree is full or not, here is what I have so far: 

    public boolean full(){
    return fullHelper(this);
}

public boolean fullHelper(BinaryTreeNode<T> node){
    if (node == null){return false;}
    if (node.left == null && node.right == null){return true;}
    if (node.left != null && node.right != null){
        return fullHelper(node);
    }
    return false;
}

The node you pass in can be the root or some arbitrary node that will check if the sub tree is full. My method keeps getting stuck on the line 

return fullHelper(node);

I was wondering why it will not pass through the line above it to check if both of the children are null. I am fairly new to both Binary Trees and recursion in general so if anyone could help explain any wrong assumptions I made it would be greatly appreciated!

Upvotes: 1

Views: 34

Answers (2)

Sometimes_Confused
Sometimes_Confused

Reputation: 181

What you want to do is iterate into the sub-nodes with the recursive call. For example:

if (node.left != null && node.right != null) {
    return fullHelper(node.left) && fullHelper(node.right);
}

Upvotes: 0

Karol Dowbecki
Karol Dowbecki

Reputation: 44952

By calling return fullHelper(node); your are reprocessing the same node you started the method with. Assuming both node.left and node.right are set this will result in an infinite recursive call and a StackOverflowException.

You need to progress the recursion to the left and right sub-nodes to check them the same way you just checked current node, e.g. you can replace the problematic line with: 

return fullHelper(node.right) && fullHelper(node.left);

Upvotes: 1

Related Questions