CODEWITHSUNDEEP
java
jollypop
jollypop

Reputation: 79

How do I calculate the number of "only child"-nodes in a binary tree?

NOTICE: this is homework-related, but I'm not tagging it as such because the 'homework' tag is marked as obselete (?)

Using the following class that implements a binary tree...

class TreeNode
{
  private Object value; 
  private TreeNode left, right;

   public TreeNode(Object initValue)
  { 
     value = initValue; 
     left = null; 
     right = null; 
  }

   public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)
  { 
     value = initValue; 
     left = initLeft; 
     right = initRight; 
  }

   public Object getValue()
  { 
     return value; 
  }

   public TreeNode getLeft() 
  { 
     return left; 
  }

   public TreeNode getRight() 
  { 
     return right; 
  }

   public void setValue(Object theNewValue) 
  { 
     value = theNewValue; 
  }

   public void setLeft(TreeNode theNewLeft) 
  { 
     left = theNewLeft;
  }

   public void setRight(TreeNode theNewRight)
  { 
     right = theNewRight;
  }

}

I need to calculate the number of nodes in the binary tree that are "only children," this being defined as a node that doesn't have another node stemming from its parent.

This is what I have so far:

public static int countOnlys(TreeNode t)
  {
     if(t == null)
         return 0;
     if(isAnOnlyChild(t))
         return 1;
     return countOnlys(t.getLeft()) + countOnlys(t.getRight());
  }

I don't know how to implement the boolean method isAnOnlyChild(TreeNode t)

Could someone please help me?

Upvotes: 3

Views: 8689

Answers (6)

Jignesh
Jignesh

Reputation: 136

public int countNode(Node root) {

         if(root == null)
             return 0;

         if(root.leftChild == null && root.rightChild == null)
             return 0;
         if(root.leftChild == null || root.rightChild == null)
             return 1 + countNode(root.leftChild) + countNode(root.rightChild);
         else
             return countNode(root.leftChild) + countNode(root.rightChild);

     }

Upvotes: -1

reddit_10
reddit_10

Reputation: 69

public static int onlyChild(TreeNode t){
    int res = 0;
    if( t != null){
        // ^ means XOR 
        if(t.getLeft() == null ^ t.getRight() == null){
            res = 1;
        }

        res += onlyChild(t.getLeft()) + onlyChild(t.getRight()));
    }

    return res;
}

Upvotes: 1

Lee Meador
Lee Meador

Reputation: 12985

A parent has an only child if exactly one of the children is non-null (which implies that exactly one of its children is null):

((t.getLeft() == null || t.getRight() == null)) && !(t.getLeft() == null && t.getRight() == null)

You don't test, however, the node when you visit it as the recursive code traverses the tree. (This is similar to the Visitor pattern.) What you do is test for an only child when you are sitting on the parent. It's actually a logical exclusive-or test because one and only one of the children needs to be non-null to detect that this node has an only child.

So the algorithm is to

  1. visit each node in the tree.
  2. count it, if the node has only one child

That's it. The rest is plumbing.

Upvotes: 1

phcoding
phcoding

Reputation: 608

As you have already noticed, one solution is to count number of parents that have only one child. This should work:

public static int countOnlys(TreeNode t)
  {
     if(t == null || numberOfChildren(t)==0){
         return 0;
     }
     if(numberOfChildren(t)==1){
         return 1+ countOnlys(t.getLeft()) + countOnlys(t.getRight());
     }
         if(numberOfChildren(t)==2 ){
         return countOnlys(t.getLeft()) + countOnlys(t.getRight());
    }
         return 0;
  }

public static int numberOfChildren (TreeNode t){
    int count = 0;
    if(t.getLeft() != null ) count++;
    if(t.getRight() != null) count++;       
    return count;   
    }

Upvotes: 2

Robert Prior
Robert Prior

Reputation: 508

You are pretty close and have the traversal looking good but in your Treenode you do not have a link between a child and its parent. So You can not tell from say a left child if a sibling (right child) exists.

You could have a parent Treenode (along with left and right) so you could check how many children a given node's parent has. Or as ajp15243 suggested, instead use a method that checks how many children a given node has.

Some pseudo code of the latter:

//we still need to check if that only child has its own children
if hasOnlyChild(t) 
      return 1 + checkOnlys(left) + checkOnlys(right)
else 
      return checkOnlys(left) + checkOnlys(right)

Upvotes: 6

75inchpianist
75inchpianist

Reputation: 4102

whenever you traverse a binary tree, think recursively. this should work.

public static int countOnlys(TreeNode t)
  {
     if(t == null)
         return 0;
     if (t.getLeft()==null&&t.getRight()==null)
         return 1;

     return countOnlys(t.getLeft())+countOnlys(t.getRight());

  }

Upvotes: 0

Related Questions