How to count the number of right children in a binary tree?

Question

How to count the number of right children in a binary tree?

This means that I only want the children marked as right.

Ex.

(Left | Right)

      F(Root)    
  G   |   H     
T   U |  I  J  

The right children would be U,H,and J.

What would be the algorithm to find these.

Answer 1

Hi,

In recursive approach,

You would be calling a function to traverse your tree, for current node, you need to: check if current node has right child (then increment the counter), and then call the function recursively for right node. check if current node has left child, call the function recursively for left node.

This should work.

Answer 2

int count(Tree *r){
    if(r == NULL) return 0;
    int num_l=0, num_r=0;
    if(r->left != NULL) 
        num_l = count(r->left);
    if(r->right != NULL) 
        num_r = count(r->right)+1;
    return num_l+num_r
}

Answer 3

You can do it recursively as:

• If tree does not exist, there are no R children.
• If tree exists, then # R children = # R children in R-subtree + # R children in L-subtree

.

  int countRChildren(Node *root) {
        if(!root)  // tree does not exist.
            return 0;

        // tree exists...now see if R node exits or not.
        if(root->right) // right node exist

            // return 1 + # of R children in L/R subtree.
            return 1 + countRChildren(root->right) + countRChildren(root->left);

        else // right nodes does not exist.
            // total count of R children will come from left subtree.
            return countRChildren(root->left);
    }

Answer 4

Do a simple traversal on the tree (i.e. post order, in order) and for each node do +1 if it has right child.

Example (didn't try to compile and check it):

int countRightChildren(Node root)
{
   if (root == null) return 0;
   int selfCount =  (root.getRightChild() != null) ? 1 : 0;
   return selfCount + countRightChildren(root.getLeftChild()) + countRightChildren(root.getRightChild());
}