CODEWITHSUNDEEP
c++calgorithmdata-structures
Utkarsh Dixit
Utkarsh Dixit

Reputation: 4275

Sample Implementation of Binary Trees doesn't work for large number of values

I have recently trying to implement a binary tree, it seems to work for less than 1000 values, but after that eventually it gives me stack overflow error

#include<iostream>
#include<math.h>

using namespace std;
struct Node{
    long long int val;
    Node *left;
    Node *right;
};
struct BinaryTree{
    Node *head  = (Node*) malloc(sizeof(Node));
    bool headSet = false;
    Node* findLast(Node *asgn,int val){
        if (val > asgn->val){
            if (asgn->right != NULL)
                asgn  = findLast(asgn->right, val);
            else
                return asgn;
        }
        else{
            if (asgn->left != NULL)
                asgn = findLast(asgn->left, val);
            else
                return asgn;
        }
        return asgn;
    }
    void insert(long long int vals){
        if (headSet){
            Node *asgn = (Node*) malloc(sizeof(Node));
            asgn = findLast(head,vals);
            Node *fix = (Node*)malloc(sizeof(Node));
            fix->val = vals;
            fix->left = NULL;
            fix->right = NULL;
            if (vals > asgn->val){
                asgn->right = fix;
                asgn->left = NULL;
            }
            else{
                asgn->right = NULL;
                asgn->left = fix;
            }
        }
        else{
            head->val = vals;
            head->right = NULL;
            head->left = NULL;
            headSet = true;
        }
    }
};
int main(){
    BinaryTree a;
    for (long long int i = 0; i < 100;i++)
    a.insert(i);

    return 0;
}

For example:- If i change 

for (long long int i = 0; i < 100;i++)
    a.insert(i);

to

for (long long int i = 0; i < 10000;i++)
    a.insert(i);

It gives me error. I can't seem to understand why this is happening, where the stack overflows?

Upvotes: 0

Views: 93

Answers (3)

Ian Abbott
Ian Abbott

Reputation: 17403

This isn't an answer as such. I just want to suggest a code change as an addendum to the original code with Michael Walz's corrections. My suggestion is to omit the headSet member and initialize the head member to NULL, and allocate head on first insert, like this:

struct BinaryTree{
    Node *head  = (Node *)NULL;
    Node* findLast(Node *asgn,int val){ // Courtesy of Michael Walz
        while (1){
            if (val > asgn->val){
               if (asgn->right != NULL)
                   asgn = asgn->right;
               else
                   return asgn;
            }
            else{
                if (asgn->left != NULL)
                    asgn = asgn->left;
                else
                    return asgn;
            }
        }
    }
    void insert(long long int vals){
        Node *fix = (Node*)malloc(sizeof(Node));
        fix->val = vals;
        fix->left = NULL;
        fix->right = NULL;
        if (head != NULL){
            Node *asgn = findLast(head,vals);
            if (vals > asgn->val){
                asgn->right = fix;
            }
            else{
                asgn->left = fix;
            }
        }
        else{
            head = fix;
        }
    }
}

Upvotes: 1

Jabberwocky
Jabberwocky

Reputation: 50774

Iterative version:

Node* findLast(Node *asgn,int val){
  while (1)
  {
    if (val > asgn->val) {
      if (asgn->right != NULL)
        asgn = asgn->right;
      else
        return asgn;
    }
    else {
      if (asgn->left != NULL)
        asgn = asgn->left;
      else
        return asgn;
    }
  }
}

Easy, isn't it ?

And the corrected version of insert:

void insert(long long int vals){
   if (headSet){
       // Node *asgn = (Node*) malloc(sizeof(Node));   // removed
       Node *asgn = findLast(head,vals);               // line changed slighty
       Node *fix = (Node*)malloc(sizeof(Node));
       fix->val = vals;
       fix->left = NULL;
       fix->right = NULL;

       if (vals > asgn->val){
           asgn->right = fix;
            //asgn->left = NULL;     // removed
       }
       else{
           //asgn->right = NULL;     // removed
           asgn->left = fix;
        }
    }
    else{
        head->val = vals;
        head->right = NULL;
        head->left = NULL;
        headSet = true;
    }
}

Upvotes: 2

Hatted Rooster
Hatted Rooster

Reputation: 36483

Your stack overflow comes from your findLast method, once the binary tree becomes too big the recursion becomes too much and overflows the call stack at one point. You should convert it into a non-recursive method by storing information about the search in some kind of structure and dynamically allocating that so that your stack doesn't fill up.

P.S use new instead of malloc in C++ and delete to clear up allocated memory, you're currently leaking memory.

Upvotes: 3

Related Questions