CODEWITHSUNDEEP
javatree
user8925274
user8925274

Reputation:

Return number of nodes with 2 children

I am working on a method that is supposed to return the number nodes in a tree that have two children. Here's what I have so far...

public int twoChild(TreeNode<Integer> root){
    if (root == null)
        return 0;
    else if (root.left != null && root.right != null)
        int leftTwoChild = twoChild(root.left);
        int rightTwoChild = twoChild(root.right);
        return 1 + leftTwoChild + rightTwoChild;

I don't think I quite have it but I may have the right idea. If anyone could guide me along on how to do this I would greatly appreciate it!

Upvotes: 0

Views: 343

Answers (1)

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

You have to test each subtree separately. The base case happens when the current tree has both children, and we count it as one for the final result - but anyway we must keep traversing the rest of the tree. This is what I mean:

public int twoChild(TreeNode<Integer> root) {

    // base case: tree is empty
    if (root == null) return 0;

    // base case: tree has both children, or not    
    int count = root.left != null && root.right != null ? 1 : 0;

    // recursive cases: traverse both subtrees, accumulating result
    count += twoChild(root.left);
    count += twoChild(root.right);

    // return result of recurring on both subtrees
    return count;

}

Upvotes: 1

Related Questions