Build minimum height BST from a sorted std::list<float> with C++

Question

I'm having trouble writing the code to build minimum height BST from a sorted std::list. For the node class:

class cBTNode
{
private:
    cBTNode* m_LeftChild;
    cBTNode* m_RightChild;
    float m_Data;
}

For the BST class:

class cBTNodeTree
{
private:
    cBTNode* m_Root;
public:
    void LoadBalancedMain(std::list<float>& ls)；
    void LoadBalanced(std::list<float>& ls, cBTNode* root);
}

Implementation: (basically my method is to find the middle element of the list ls, put that into the root, put all the elements smaller than the middle element into ls_left, and all the elements bigger than it into ls_right. Then recursively build up the left and right subtree by recursively calling the same function on ls_left and ls_right)

void cBTNodeTree::LoadBalancedMain(std::list<float>& ls)
{
    LoadBalanced(ls, m_Root); // m_Root is the root of the tree
}

void cBTNodeTree::LoadBalanced(std::list<float>& ls, cBTNode* root)
{
     // Stopping Condition I:
    if (ls.size() <= 0)
    {
        root = nullptr;
        return;
    }

    //  Stopping Condition II:
    if (ls.size() == 1)
    {
        root = new cBTNode(ls.front());
        return;
    }

    //  When we have at least 2 elements in the list
    //  Step 1: Locate the middle element

    if (ls.size() % 2 == 0)
    {
        //  Only consider the case of even numbers for the moment
        int middle = ls.size() / 2;
        std::list<float> ls_left;
        std::list<float> ls_right;
        int index = 0;

        // Obtain ls_left consisting elements smaller than the middle one
        while (index < middle)
        {
            ls_left.push_back(ls.front());
            ls.pop_front();
            index += 1;
        }
        //  Now we reach the middle element
        root = new cBTNode(ls.front());
        ls.pop_front();
        //  The rest is actually ls_right
        while (ls.size() > 0)
        {
            ls_right.push_back(ls.front());
            ls.pop_front();
        }
        //  Now we have the root and two lists
        cBTNode* left = root->GetLeftChild();
        cBTNode* right = root->GetRightChild();
        if (ls_left.size() > 0)
        {
            LoadBalanced(ls_left, left);
            root->SetLeftChild(left);
        }
        else
        {
            left = nullptr;
        }
        if (ls_right.size() > 0)
        {
            LoadBalanced(ls_right, right);
            root->SetRightChild(left);
        }
        else
        {
            right = nullptr;
        }
    }
} 

My Question: Somehow I found that actually none of the elements has been inserted into the tree. For example, if I check the value of m_Root, the root of the tree, I got an error because it's still nullprt. I'm not sure where did I go wrong? I hope it's some stupid pointer mistake because I haven't slept well. (I'm pretty sure the 'new cBTNode(ls.front())' line works)

BTW although I have written a dozen functions for the BST, I'm still struggling with BST recursion. I noticed that in all the textbooks that I read, for the linked list version of BST, the insertion ALWAYS need a helper function that return a pointer to a node. I begin to feel that I don't actually understand the things going on behind the recursion...

Answer 1

1:

void cBTNodeTree::LoadBalanced(std::list<float>& ls, cBTNode* root)

Here cBTNode* root is passed by value.

Instead, you should pass by reference & or cBTNode** (pointer to a pointer).

Passing by reference would be simple, you won't need to change anything except the function signature.

void cBTNodeTree::LoadBalanced(std::list<float>& ls, cBTNode*& root)

Notice & before root in above statement.

2:

if (ls_right.size() > 0)
        {
            LoadBalanced(ls_right, right);
            root->SetRightChild(left);
        }

You are setting right child to left root which is not what you desire.

3:

cBTNode* left = root->GetLeftChild();
cBTNode* right = root->GetRightChild();

These are unnecessary.

4:

if (ls.size() % 2 == 0)

No need for two separate cases.

You can achieve this by just appropriately setting middle:

int middle = (ls.size()-1) / 2;

Answer 2

You pass the pointer to the root by value. Pass it by reference instead by changing the signature of LoadBalanced() appropriately.