How to change my function into a constructor?

Question

I need to make a parametrized constructor that creates a perfectly balanced binary search tree given a sorted array. I know how to make a function that creates the BST but how can I make the BST from a constructor? This is my function:

    node * sortedArrayBST(double * arr, int start, int end)
    {
        int mid = (start + end)/2;
        if (start > end)
        {
            return NULL;
        }
        //because the array will be sorted
        //the root of the tree will contain the item in the middle of the array so everything less than the middle will go in the left subtree
        //and everything greater than the middle will go in the right subtree

        node * root = new node(arr[mid]);
        //recursively make left subtree
        root->left = sortedArrayBST(arr, start, end-1);
        //recursively make left subtree
        root->right = sortedArrayBST(arr, mid + 1, end);

        return root;
    }

Constructor doesn't have return type, how are you going to return node *? — Killzone Kid, Apr 17 '18 at 23:39
I wish a had a penny every time a see a downvote when a newbie is asking for help... — ipavlu, Apr 17 '18 at 23:40
Constructors must be members of structs/classes. You need a struct or a class. — , Apr 17 '18 at 23:40
To be pedantic (but aren't we all on SO). `int mid = (start + end)/2;` has a potential issue that it might overflow the int if the values are large enough. For more info see [here](https://stackoverflow.com/questions/6735259/calculating-mid-in-binary-search). Not likely you'd use an array that large but still a theoretical possibility. — Paul Rooney, Apr 18 '18 at 00:30
Hint for your effort: see my answer at https://stackoverflow.com/a/45514477/2785528. Note that I have two cooperating classes: BTree_t and Node_t. Separating these issues allows BTree_t to contain "Node_t* m_root", i.e. a place to hold the root of one tree. Btree methods check various tree issues, (full or empty, etc.) but generally invoke m_root->methodX(); where the various methods are the details of node insert, showTallView, searchR [Recursive], showBR [BreadthFirst, or wide view Recursive], showDFioR [depth first, in-order, Recursive], etc. (I like recursion!) — 2785528, Apr 18 '18 at 01:31

score 0 · Accepted Answer · 2018-04-18T00:41:32.087

0

class BST
{
public:
      BST (double * arr, int start, int end)
      {
          int mid = (start + end)/2;
          if (start > end)
          {
              std::cerr << "Invalid BST tree."
          }
          //because the array will be sorted
          //the root of the tree will contain the item in the middle of the array so everything less than the middle will go in the left subtree
          //and everything greater than the middle will go in the right subtree

          root = new node(arr[mid]);
          node *temp, *parent;
          for (num = arr[mid/2]; start <= end;)
             if (num <= arr[end]){
                parent = temp;
                temp=temp->left;
                end = (start + end)/2;
             } else {
                parent = temp;
                temp=temp->right;
                start = (start + end)/2;
             }
          }
          //recursively make left subtree
          root->right = sortedArrayBST(arr, mid + 1, end);
      }
private :
      node * root;
}

edited Apr 18 '18 at 00:41

answered Apr 17 '18 at 23:43

Constructors cannot return anything. `node * root ` is a local variable of the constructor, so you have a memory leak, and the constructor doesn't work. `node root;` isn't a pointer. – Apr 17 '18 at 23:45
UPS my bad @NeilButterworth, I will fix it right away :) – Apr 17 '18 at 23:46
Please add a method returning the node*, this way data are lost in the class forever :). – ipavlu Apr 17 '18 at 23:51
@ipavlu His edited code is setting the root member variable, so nothing is lost. – Apr 17 '18 at 23:52
I am missing somebody/something that can use the root. – ipavlu Apr 17 '18 at 23:58
According to your code, I would keep the sortedArrayBST function and just call it from the constructor? – Josh Garza Apr 18 '18 at 00:00
@JoshGarza you can do that, I had non recursive version where you do not need to `sortedArrayBST()` at all. – Apr 18 '18 at 00:01
@GRC In your original post, it has the constructor calling sortedArrayBST() to build the left and right subtree. Maybe it hasn't updated? – Josh Garza Apr 18 '18 at 00:04
@ipavlu This is not compilable code, so adding accessor functions is not really germane. If you want to be picky, he also needs a destructor et al, and a semicolon at the end of the class definition. – Apr 18 '18 at 00:05
@JoshGarza I just found it right now, I will insert the code soon – Apr 18 '18 at 00:14
Can we please stop making it personal? I am not picky, I was pointing to one issue even when there are more, usually helps to authors start to analyze own work and improve multiple things in one step. Rather than a totally negative list of all wrongdoings which I wanted to avoid. I am in a good mood before sleep:). – ipavlu Apr 18 '18 at 00:17
@ipavlu thanks for your points, I am improving my answer as I go. And please point to the mistakes I do have. Sometimes I miss something obvious like `return NULL` pointed by neil above. – Apr 18 '18 at 00:20
1

Wouldn't it be better to just call `sortedArrayBST` straight away in the constructor? To avoid code repetition. i.e. `root = sortedArrayBST(arr, start, end);` – Paul Rooney Apr 18 '18 at 00:25
@PaulRooney it would :) but I like challenges :) – Apr 18 '18 at 00:27
@JoshGarza This proved to be more challenging but bare with me :) – Apr 18 '18 at 00:36
1

Some architectural thinking, methods like sortedArrayBST are often included into private parts of the class. Further processing of result is then inside the class if you need just one kind of processing. If not, then data can be shared outside as a pointer or reference or better, through inheritance data can be accessed by specific processing implementation, access has to be protected to make it visible. – ipavlu Apr 18 '18 at 00:45
@ipavlu I agree totally. I was trying to use fact that I was given sorted array as advantage, but I think I will have to use different approach. – Apr 18 '18 at 00:47
guys this is not really an answer, I am gonna sleep on it. :( – Apr 18 '18 at 01:12

How to change my function into a constructor?

1 Answers1