0

I have already some sort of solution for the problem:

Given an integer N, construct all possible binary search trees with N nodes.

except that I include trees with root the minimum and maximum value but this is not my main concern. I want to put emphasis into correctly using the move semantics and memory management in C++ (as a learning exercice).

My solution is:

#include <vector>

struct Node{
    int value;
    Node *left = nullptr;
    Node *right = nullptr;
};

std::vector<Node*> createListNodes(int min, int max)
{
    // ordered vector with i.e. {0,1,2,3,4}
    Node *node = new Node;
    if (min == max)
    {
        node->value = min;
        return std::vector<Node*> {node}; // it is a leaf node
    }
    std::vector<Node*> alterantive{};
    for (int i=min; i<=max; i++)
    {
        auto left = createListNodes(min,i-1); // for the left side
        auto right = createListNodes(i+1,max); // for the left side
        if (left.size() == 0) // if node i has just one child and it is in the right
        {
            for (auto elem_right : right)
            {
                alterantive.emplace_back(new Node{i,nullptr,elem_right});
            }
        }
        else if (right.size() == 0) // if node i has just one child and it is in the left
        {
            for (auto elem_left : left)
            {   
                alterantive.emplace_back(new Node{i,elem_left,nullptr});
            }
        }
        for (auto elem_left : left)
        {
            for (auto elem_right : right)
            {
                alterantive.emplace_back(new Node{i,elem_left,elem_right});
            }
        }
    }
    return alterantive;

}

int main()
{
    int N = 4;
    std::vector<Node*> combinations = createListNodes(0, N);
}

So would like to know:

  1. Improvements I could made to my basic design, I would prefer not to use smart pointers yet but the raw ones, to make it more memory efficient (copying less values from one side to the other ...)
  2. General improvements in the code, even though my main focus is on memory management, memory leaks ...
Hector Esteban
  • 1,011
  • 1
  • 14
  • 29
  • 1
    *I want to put emphasis into correctly using the move semantics and memory management in C++ (as a learning exercice).* -- Create real BST objects, not simply a vector of pointers. Your code leaks memory due to not able to clean up the memory you allocated. – PaulMcKenzie Apr 23 '20 at 10:00
  • but if after getting the result from the createListNodes function I remove all the nodes there is no memory leakage isnt it? – Hector Esteban Apr 23 '20 at 10:06
  • All of that removal should be encapsulated in a class and in the destructor. The client caller (`main`) shouldn't care how that tree is put together. That's the C++ way of doing this. – PaulMcKenzie Apr 23 '20 at 10:09
  • but if I have to return the result on the main I cannot delete it before – Hector Esteban Apr 23 '20 at 10:17
  • 1
    `int main() { auto v = getCombinations(x, y); Print(v); }` The `v` is *not* deleted until after `main` returns. The `v` is the vector of trees. Are you familiar with when a destructor is invoked? – PaulMcKenzie Apr 23 '20 at 10:18
  • Maybe you should [read what RAII is](https://stackoverflow.com/questions/2321511/what-is-meant-by-resource-acquisition-is-initialization-raii) – PaulMcKenzie Apr 23 '20 at 10:23

0 Answers0