Have Geek Brain

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

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

This means that I want the kids to be tagged as correct.

Ex.

(Left | Right)

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

The correct children are U, H and J.

What will be the algorithm for finding them.

+2


a source to share


5 answers 


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
}


+6


a source


In a recursive approach

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



This should work.

+1


a source


Simple tree traversal (i.e. order in order) and for each node do +1 if it has the correct child.

Example (didn't try to compile and test 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());
}
+1


a source


You can do it recursively like:

  • If the tree does not exist, there are no R children.
  • If the tree exists, then # R children =

    # R children in the R subtree +

    # R children in the 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);
    }
0


a source


This includes how I am building 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);
}
0


a source






More articles:


All Articles