Tree using recursive programming

Question

Given a tree and some integer k, verify if the sum of the right subtree is greater than the (sum of the left subtree * k) for each subtree.

The output should be a vector containing the node values for all nodes of the tree for which the above condition is true, sorted in ascending order.

Here is the code:

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
  int info;
  node* right;
  node* left;
};
int sommatuttechiavi(node*& tree){
  if (tree == nullptr){
    return 0;
  }
  else{
    return tree->info + sommatuttechiavi(tree->left) + sommatuttechiavi(tree->right);
  }
}
int sommachiavidestra(node*& tree){
  if (tree == nullptr){
    return 0;
  }
  tree = tree->right;
  return sommatuttechiavi(tree);
}
int sommachiavisinistra(node*& tree){
  if (tree == nullptr){
    return 0;
  }
  tree = tree->left;
  return sommatuttechiavi(tree);
}
void insert(node*& tree, int info){
  if (tree==nullptr){
    tree = new node;
    tree->info = info;
    tree->left = nullptr;
    tree->right = nullptr;
  }
  else{
    if (tree->info > info){
        insert(tree->left, info);
    }
    else{
        insert(tree->right, info);
    }
  }
  return;
}
void checkpropety(node*& tree, vector<int>& isok, int k){
  if (tree==nullptr){
    return;
  }
  else{
    if ((sommachiavisinistra(tree)*k) < sommachiavidestra(tree)){
        isok.push_back(tree->info);
    }
    checkpropety(tree->left, isok, k);
    checkpropety(tree->right, isok, k);
    return;
  }
}
bool ordina(const int& asd, const int& dsa){
  if (asd < dsa){
    return true;
  }
  else{
    return false;
  }
}
int main(){
  vector<int> resultset;
  node* root = nullptr;
  int n, k;
  cin >> n;
  cin >> k;
  for (int i = 0; i < n; i++){
    int t;
    cin >> t;
    insert(root, t);
  }
  checkpropety(root, resultset, k);
  sort(resultset.begin(), resultset.end(), ordina);
  for (unsigned i = 0; i < resultset.size(); i++){
    if (i == resultset.size() - 1){
        cout << resultset[i];
    }else{
        cout << resultset[i] << ' ';
    }
  }
  return 0;
}

I tested the program a few time with Dr. Memory and it detects this errors:

Error #1: UNADDRESSABLE ACCESS: reading 0x00000008-0x0000000c 4 byte(s)
# 0 checkpropety               [{a lot of directory}\test_esame2.cpp:51]
# 1 checkpropety               [{a lot of directory}\test_esame2.cpp:58]
# 2 main                       [{a lot of directory}\test_esame2.cpp:82]

I checked this function all day with no result. Can someone help me?? Thanks in advance, and sorry for my bad english.

Apart from the Dr.Memory message, how does the code fail? Runtime errors? — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented May 12, 2015 at 14:06
it let me insert all the input, and then show this window: "nomeofprogram.exe stopped to work" screen: i58.tinypic.com/35c53tg.jpg — w0nderwall
– w0nderwall, Commented May 12, 2015 at 14:08
I assume you have a source-level debugger at your disposal. It crashes pretty quickly, so it should be easy to see exactly what is happening by just stepping through the code. — Brent Bradburn
– Brent Bradburn, Commented May 12, 2015 at 14:23
you should be carefull when passing a pointer as node *&, if you change the pointer in the function , the change will remain after the call(aka you lost the original tree) — niceman
– niceman, Commented May 12, 2015 at 14:25

Jeff Ames · Accepted Answer · 2015-05-12 14:26:36Z

2

You might not want to pass tree as a reference to sommachiavisinistra and sommachiavidestra, since that will also modify the caller's version of tree. In checkpropety, it seems like by the time you get to the checkpropety(tree->left, isok, k) recursive call, tree will already be nullptr.

Side note: ordina should just take int arguments, not const int&. And it could be shortened to one line: return (asd < dsa);

edited May 12, 2015 at 14:26

answered May 12, 2015 at 14:17

Jeff Ames

1,44610 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

molbdnilo · Accepted Answer · 2015-05-12 14:25:28Z

1

Your summation functions are altering the tree:

int sommachiavidestra(node*& tree){
  if (tree == nullptr){
    return 0;
  }
  tree = tree->right;
  return sommatuttechiavi(tree);
}

will set the parameter to its own right subtree.

Since you recurse when checking the "property", you will reach a point where after (sommachiavisinistra(tree)*k) < sommachiavidestra(tree), tree is null, and you get an invalid read.

Do this instead:

int sommachiavidestra(const node* tree){
  if (tree == nullptr){
    return 0;
  }
  return sommatuttechiavi(tree->right);
}

and similarly for the left subtree.

There is also no reason for sommatuttechiavi or checkPropety to take a reference parameter.

answered May 12, 2015 at 14:25

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

Collectives™ on Stack Overflow

Tree using recursive programming

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related