CODEWITHSUNDEEP
javarecursiontreebinary-tree
Dominik J
Dominik J

Reputation: 39

Recursive check of a binary tree in Java

here's a little problem from the following Java puzzle (http://code-exercises.com/programming/medium/28/strict-binary-tree-check). The task is to write a method that checks whether in a given binary tree all of the nodes have either 0 or 2 child nodes.

Their solution is the following 

public Boolean isStrictTree(TreeNode node) {
    if (node == null) {return true;}
    if ((node.left() == null && node.right() != null) || (node.left() != null && node.right() == null)) {return false;}

    return isStrictTree(node.left()) && isStrictTree(node.right());
}

I came up with something similar, but it doesnt work. The difference is

a) 1st line - handling the null case (returns "null" instead of "true")

b) the structure of the recursion - mine is somehow jumbled together (in a way which should work if i trace it what happens a piece of paper) as opposed to the solution spreading it out over two lines - the conditional and the return statement.

public Boolean isStrictTree(TreeNode node) {
    if (node == null) {return null;}

    else if ((isStrictTree(node.left()) == true) && (isStrictTree(node.right())==null)) {return false;}

    return true;
}

The script runs but doesnt return anything. I'd be really interested to understand WHY it doesnt work, it seems theres something I can learn here, so any insight is appreciated.

Upvotes: 1

Views: 567

Answers (1)

upf
upf

Reputation: 106

You have two options: Either the node is valid/balanced, then return true or the node is invalid/imbalanced, the return false. Why is it that you want to introduce a third state - null? There is no need for that thing.

Why it's not working: In (isStrictTree(node.left()) == true your call to isStrictTree(...) will return null at some point in time, so you get an NullPointerException when comparing it to true.

Upvotes: 2

Related Questions