java - tree structure method

Question

I've been asked to write a recursive method to investigate whether or not there are any single children. I have get the base cases but am a bit confused about how to go about the recursive section as I will need to investigate both the right and the left subtree and return false if one of them has a single child and true if one of them has 0 children or recur.

what I have so far is:

public static boolean noSingleChildren( BinaryTreeNode t ) { 
    if (rightC == null || leftC == null) {
         return false;
    } else if (rightC == null && leftC == null) {
        return true;
    } else {
        return............
    }
}

It would be much easier if the method was singleChildrenExists() rather than noSingleChildren(). — JB Nizet
– JB Nizet, Commented May 4, 2012 at 15:08

NPE · Accepted Answer · 2012-05-04 15:09:34Z

2

The logic is quite simple:

If the current node only has a single child, you're done.
Otherwise, recursively ask each non-null child the same question, and combine the answers using logical "or".

Since this looks like homework, I leave the implementation to you.

answered May 4, 2012 at 15:09

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Aram Arabyan · Accepted Answer · 2012-05-04 15:10:04Z

1

public static boolean noSingleChildren( BinaryTreeNode t ) { 
    if (rightC == null || leftC == null) {
         return false;
    } else if (rightC == null && leftC == null) {
        return true;
    } else {
        return noSingleChildren(t.getLeftBranch()) || noSingleChildren(t.getRightBranch());
    }
}

answered May 4, 2012 at 15:10

Aram Arabyan

2,3591 gold badge18 silver badges31 bronze badges

Comments

shem · Accepted Answer · 2012-05-04 15:10:53Z

1

Ho, I love trees questions:

public static boolean hasSingleChildren( BinaryTreeNode t ) { 
    if (t == null) {
         return false;
    } else if (t.rightC == null && t.leftC != null) {
        return true;
    } else if (t.rightC != null && t.leftC == null) {
        return true;
    } else {
        return hasSingleChildren(t.rightC) || hasSingleChildren(t.leftC);
    }
}

answered May 4, 2012 at 15:10

shem

4,7222 gold badges34 silver badges43 bronze badges

Collectives™ on Stack Overflow

java - tree structure method

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related