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

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

This means that I only want the childr开发者_运维技巧en 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.

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
}

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.

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());
}

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);
    }

This is include how i build the struct

 struct Item
 {
   int info;
   struct Item* right;
   struct Item* left;
 };
 typedef struct Item* Node;

int countRightSons(Node tree)
{
  if(!tree)
    return 0;
  if(tree->right != NULL)
    return 1 + countRightSons(tree->right) + countRightSons(tree->left);
   return countRightSons(tree->left);
}

Simple recursive approach, check (even if not needed) for all the 4 possibilities:

1. left and right does not exists

2. left and right exists

3. left exists and right doesnt

4. right exists and left doesnt

    public static int countRightChildren(BST tree) {
        if (tree.root==null) return Integer.MIN_VALUE;
        return countRightChildren(tree.root);}
   
   
    public static int countRightChildren(Node curr) {
   
    if (curr.right==null&&curr.left==null) return 0;
    else if (curr.right!=null&&curr.left==null) 
        return curr.right.data+countRightChildren(curr.right);
    else if (curr.right==null&&curr.left!=null)
        return countRightChildren(curr.left);
    else if (curr.right!=null&&curr.left!=null) 
        return curr.right.data+countRightChildren(curr.left)+countRightChildren(curr.right);
   
    return Integer.MIN_VALUE;
    }