Check if binary search tree contains more evens numbers than odds

user_6908317 0
Viewed 86

I want to implement a function to check if a BST (of int values) contains more odds it should return 2, if it contains more evens return 1 and 0 otherwise - recursively.

I was trying to create help function with inputs of even and odd counter but the function returns wrong output.

My code:

int evenOdd(Tnode* root) {
    if (root == NULL)
        return 0 ;
    return eVenOddHelp(root , 0 , 0) ;
}

int eVenOddHelp(Tnode* root , int even , int odd) {
    if (root == NULL) {
        if (even > odd)
            return 1 ;
        else if (odd > even)
            return 2 ;
        return 0 ;
    }
    else {
        if (root->data % 2 == 0) {
            eVenOddHelp(root->left , even + 1 , odd) ;
            eVenOddHelp(root->right , even + 1 , odd) ;
        }
        else {
            eVenOddHelp(root->left , even , odd + 1) ;
            eVenOddHelp(root->right , even  , odd + 1) ;
        }
    }
}
binary-search-tree recursion c algorithm
2 Answers

IMO the easiest way is to use the return value, if return positive there are more evens, if negative there are more odds, 0 otherwise:

int evenOdd(Tnode* root) {
    int result = eVenOddHelp(root);
    if(result > 1) return 1;       // More evens
    else if(result == 0) return 0; // the same 
    else return 2;                 // More odds
}

int eVenOddHelp(Tnode* root) {
    if (root != NULL) {
       int isEven = (root->data % 2 == 0) ? 1 : -1;
       return eVenOddHelp(root->left) + eVenOddHelp(root->right) + isEven;
    }
    return 0;
}

Comparing like this:

if (root == NULL) {

    if (even > odd)
        return 1 ;
    else if (odd > even)

        return 2 ;
    return 0 ;

}

Will produce wrong values because there is several times where the root == NULL is true, you will comparing evens and odds in different subtrees. And not at the end of the entire tree.

user_13668710

There's an easier way to do this by using counters passed in as mutable pointers:

void modCounter(Tnode* node, int* even, int* odd) {
  if ((node->data % 2) == 0) {
    (*even)++;
  }
  else {
    (*odd)++;
  }

  if (node->left) {
    modCounter(node->left, even, odd);
  }

  if (node->right) {
    modCounter(node->right, even, odd);
  }
}

Note that it just alters the pointed values, so you call it like this:

int evenOdd(Tnode* root) {
  if (root == NULL)
    return 0;

  int even = 0;
  int odd = 0;

  modCounter(root, &even, &odd);

  if (even > odd) {
    return 1;
  }

  if (odd > even) {
    return 2;
  }

  return 0;
}

To use a more C-based approach you could even pass in an array of two int values, as in:

void modCounter(Tnode* node, int* counters, int mod) {
  ++counters[node->data % mod];

  // ...
}

Where you call it like this:

int counters[2];

modCounter(root, &counters[0], 2);
user_871890
Related