2
\$\begingroup\$

I want to easily create a binary tree given an array. The array elements are processed in a level order manner. E.g. If the array contains:

{19,10,43}

Then the root is 19, left child is 7 and right child is 3. To declare that the node does not have a child, I'm using a special data value as infinity marker.

E.g. {19,10,43,7,12,END_MARKER,50} becomes like this:

    19
   /  \
  10  43
 / \    \    
7   12  50

here, 43 has no left child because it is marked by END_MARKER.

The function that does the conversion is as follows:

/*
 * Create a BST from the given vector. Use nullMarker to specify that the data element
 * does not exist. For example, if there is no left child of a node, place nullMarker as it's value.
 * When passing the initVector to create bst, follow the heap property.
 */
template <typename T>
BinaryTree<T>::BinaryTree(const vector<T>& initVector,T nullMarker) {

    if(initVector.size() == 0 || initVector[0] == nullMarker)
        return;

    queue<reference_wrapper<unique_ptr<BinarySearchNode<T>>>> q;
    this->root = make_unique<BinarySearchNode<T>>(initVector[0]);
    q.emplace(this->root);

    size_t lastIndex = initVector.size()-1;

    size_t index = 0; // MUST start with index = 0
    while (!q.empty() && (index + 2) < lastIndex) {

        auto current = q.front();

        T left = initVector[index+1];
        T right = initVector[index+2];


        if(left != nullMarker) {
            current.get()->leftChild = make_unique<BinarySearchNode<T>>(left);
            q.emplace(current.get()->leftChild);
        }

        if(right != nullMarker) {
                current.get()->rightChild = make_unique<BinarySearchNode<T>>(right);
                q.emplace(current.get()->rightChild);
        }

        index+=2;
        q.pop();
    }

    // Two possible cases
    // 1. There is one left child remaining.
    // 2. There are no more

    if(index != lastIndex) {
        auto current = q.front();

        if(initVector[++index] != nullMarker) {
            current.get()->leftChild = make_unique<BinarySearchNode<T>>(initVector[index]);
        }

        index++;

        if(index <= lastIndex) {
            current.get()->rightChild = make_unique<BinarySearchNode<T>>(initVector[index]);
        }
    }
}

BinarySearchNode is created but I'm thinking I should call it binary node instead.

BinaryTree class is defined as follows:

template <typename T>
class BinaryTree {
public:
    BinaryTree(const vector<T>& initVector,const T nullMarker);
    unique_ptr<BinarySearchNode<T>>& getRoot() { return root; }
private:
    void populateBinaryNode(BinarySearchNode<T>& parent, vector<T> source);
private:
    unique_ptr<BinarySearchNode<T>> root = nullptr;
};

BinarySearchNode itself is defined as follows:

template <typename T>
class BinarySearchNode {

public:
    unique_ptr<BinarySearchNode<T>> leftChild;
    unique_ptr<BinarySearchNode<T>> rightChild;

    BinarySearchNode(T pData) : data(pData), leftChild(nullptr), rightChild(nullptr) {}
    BinarySearchNode(T pData, unique_ptr<BinarySearchNode<T>> pLeft, unique_ptr<BinarySearchNode<T>> pRight)
    : data(pData),leftChild(move(pLeft)), rightChild(move(pRight)) {}

    T getData() const { return data; };

private:
    T data;
};

Following is an example of how I'm using it:

int END_MARKER = numeric_limits<int>::min();

BinaryTree<int> bst(
                    {
                        19, // 0 l = 1, r = 2
                        7, // 1 l = 3, r = 4
                        43, // 2 l = 5, r = 6
                        3,  // 3 l = 7, r = 7
                        11, // 4 l = 9, r = 10
                        23, // 5 l = 11, r = 12
                        47, // 6 l = 13, r = 14
                        2,  // 7 l = 15, r = 16
                        5,  // 8 l = 17, r = 18
                        END_MARKER, // 9
                        17, // 10 l = 21, r = 22
                        END_MARKER, // 11
                        37, // 12 l = 25, r = 26
                        END_MARKER, // 13
                        53, // 14 l = 28
                        END_MARKER,
                        END_MARKER,
                        END_MARKER,
                        END_MARKER,
                        13,
                        END_MARKER,
                        29,
                        41,
                        END_MARKER,
                        END_MARKER,
                        END_MARKER,31
                    },
                    END_MARKER);
\$\endgroup\$
  • \$\begingroup\$ That kind of sentinel won't work well for a general value T. Simply using nullptr's for the left and right node should suffice. \$\endgroup\$ – πάντα ῥεῖ Apr 10 '17 at 21:58
  • \$\begingroup\$ I used the sentinel so the user can pass the right sentinel for the general data type T. Since the array which I'm parsing to convert to tree contains only data value of type T, I don't know how to specify a nullptr. I looked at the C++ standard reference, nullptr is a nullptr_t which is a null pointer constant. I'm not sure if I can pass a nullptr in a non-pointer data types? I will append my question with how I'm using the DS. \$\endgroup\$ – user1044328 Apr 10 '17 at 22:32
  • \$\begingroup\$ But there might be T's that doesn't allow the user to determine a reasonable one, so your generic implementation would become useless for them. \$\endgroup\$ – πάντα ῥεῖ Apr 10 '17 at 22:36
  • \$\begingroup\$ That is right. Can you please suggest how I might work around? I cannot insert nullptr in a vector of int or generic datatype T. Is there an idiomatic way or a pattern I can use. The only other thing, I can think of is to have a seperate list of indices which serves as end marker. So if I want to say {19,-,25} and I want to say 19 has no left child then i can pass sentinel array {1}, here since index 1 is in the sentinel array, it means it is being treated as a sentinel. It burdens the user though and makes it harder to use. \$\endgroup\$ – user1044328 Apr 10 '17 at 22:42
  • \$\begingroup\$ You already have those unique_ptr<BinarySearchNode<T>> for the leftChild and rightChild members. A std::unique_ptr can hold a nullptr, so why hassling with the sentinel value at all? \$\endgroup\$ – πάντα ῥεῖ Apr 10 '17 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.