CODEWITHSUNDEEP
cfunctionbinary-search-tree
untitled
untitled

Reputation: 49

BST; the sum of BST elements which are greater then the sum of their direct children

So the task is to write a function which returns the sum of BST elements which are greater then the sum of their direct children. Do not count leaf nodes. I did it this way, the base case when the tree is empty return 0, and if it doesn't have sons also return 0. Then I checked if node has one or two children and the condition for the sums.

int sum(struct node* root) 
{
if (root== NULL) return 0;
if (root->right == NULL && root->left==NULL) return 0;
if (root->right!= NULL && root->left != NULL)
{
    if (((root->right)->key + (root->left)->key) < root->key) return root->key;
}
if (root->right != NULL && root->left==NULL)
{
    if ((root->right)->key< root->key) return root->key;
}
if (root->left != NULL && root->right==NULL)
{
    if ((root->left)->key < root->key) return root->key;
}
else return sum(root->right) + sum(root->left);
}

Main:

struct node* root = NULL;

add(&root,-4);
add(&root,6);
add(&root,8);
add(&root,-11);
add(&root,5);
add(&root,7);
add(&root,-20);
printf("%d",sum(root));

It should return -1 (6+8-11-4), but my function doesn't work I don't know why.

Upvotes: 0

Views: 65

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 754570

In your code, the else clause will never be executed; your previous conditions have dealt with all possibilities.

However, the expression should be executed. You either need to add + sum(root->left) + sum(root->right) as part of the three non-degenerate return statements, or you need to save the root->key in a local variable (defaulting to zero) and fall through to return return_value + sum(root->left) + sum(root->right);.

Hence (using the abbreviation rv for 'return value':

int sum(struct node* root)
{
    int rv = 0;
    if (root == NULL || (root->right == NULL && root->left == NULL))
        return rv;
    if (root->right != NULL && root->left != NULL)
    {
        if ((root->right->key + root->left->key) < root->key)
            rv = root->key;
    }
    if (root->right != NULL && root->left == NULL)
    {
        if (root->right->key < root->key)
           rv = root->key;
    }
    if (root->left != NULL && root->right == NULL)
    {
        if (root->left->key < root->key)
            rv = root->key;
    }
    return rv + sum(root->right) + sum(root->left);
}

Warning: pristine code, unsullied by any attempt to compile it.

You could use an else if chain for the last three 'outer' if tests (with an else clause instead of the last test) to avoid repeated tests. Whether there'd be a measurable difference is debatable; an optimizer might even make the change for itself.

Upvotes: 1

Related Questions