Convert an array to a binary tree

Question

I wrote this code in C++ to convert an array to a binary tree.

For instance, int nums[] = {7,5,9,1,7,3} to a binary tree (root-7, root's left child-5, root's right child-9...).

( here, I made a function named 'create_tree()' which only take one argument )

Is there any shorter way to do this?

#include <iostream>
#include <cstdlib>
#include <cstdio>

template<class E>
struct TNode{
    E value;
    TNode<E>* leftChild;
    TNode<E>* rightChild;

    TNode<E>(){
        this->value = NULL;
        this->leftChild = NULL;
        this->rightChild = NULL;
    }

    TNode<E>(E value){
        this->value = value;
        this->leftChild = NULL;
        this->rightChild = NULL;
    }
};

template<class E>
class BTree{
private:
    TNode<E>* root;

    /**
        build and return the pointer to a binary tree for given array 'arr' and array         size 'len'
    */
    TNode<E>* build(E* arr, int len){

        TNode<E> *subRoot = new TNode<E>(arr[0]);
        if (len == 1){
            return subRoot;  // terminating function - at the leaf
        }
        E* elementsToLeft = new E[len];  // array to store the left subtree children
        E* elementsToRight = new E[len];  // array to store the right sub tree     children

        int counterLeft = 0;  
        int counterRight = 0;

        for (int i = 1; i < len; i = (i * 2) + 1){
            for (int j = i; j < i + ((i + 1) / 2); j++){
                elementsToLeft[counterLeft] = arr[j]; // appending the array which     has children of left sub tree
                counterLeft++;
                if ((j + (i + 1) / 2)<len){  // check whether there are childs to     store in the right sub tree....
                    elementsToRight[counterRight] = arr[j + (i + 1) / 2]; //   appending the array which has children of left sub tree
                    counterRight++;
                }

            }
        }
        subRoot->leftChild = build(elementsToLeft, counterLeft);  // recursive call>     array- left sub tree's children and size
        subRoot->rightChild = build(elementsToRight, counterRight); // recursive     call> array- right sub tree's children and size
        return subRoot;
    }

public:

    /**
    add the value specified by newvalueas the left child of the tree node specified     by parent,if the node does not have a left childalready.
    returns 1 if addition is successful and returns -1 in failure.
    */
    template <class E>
    int intaddLeftChild(TNode<E>* parent, E newvalue){
        if (parent->leftChild != NULL){ return -1; }
        TNode<E> *temp = new TNode<E>(newvalue);
        parent->leftChild = temp;
        return 1;
    }

    /**add the value specified by newvalueas the right child of the tree node     specified by parent, if the node does not have a right childalready.
    returns 1 if addition is successful and returns -1 in failure.
    */
    template <class E>
    int intaddRightChild(TNode<E>* parent, E newvalue){
        if (parent->rightChild != NULL){ return -1; }
        TNode<E> *temp = new TNode<E>(newvalue);
        parent->rightChild = temp;
        return 1;
    }

    /**
    function to create and return the pointer to a Binary tree from an array
    input an array. eg:- int i[] = {3,5,7} ; create_tree(i);
    */
    template<class E, int N>
    TNode<E>* create_tree(E(&elements)[N]){
        int length = N;
        return build(elements, N);
    }
};

int main(){
    //to demonstrate
    int nums[] = { 7,5,9,1,7,3};
    BTree<int> mal;

    TNode<int>* BinaryTree = mal.create_tree(nums); // store the made binary tree     from nums and point it by the pointer, BinaryTree.


}

Answer 1

Template parameters

template<class E>

In C++ we usually use T for generic template type parameters.

Nest implementation classes

The class TNode is an implementation detail of BTree and should thus be a nested class. Normally we prefer terse but descriptive names, TreeNode would be preferred to TNode but even better, if TNode is nested you can simply use Node as it will always be clear from context that it is a binary tree node.

General comments on TNode:

• Prefer to use C++11 style member initialization to avoid some duplication.
• Please do prefer nullptr to NULL since C++11.
• You do not need to repeat the template argument inside the template.
• You could use move semantics on the constructor but I will not do so here.
• Also, we rarely use this-> for qualifying member variables. I prefer to use a prefix on member variable names, m_ to make them stand out and avoid confusion.
• You should have a destructor and the typical semantic is for it is to destroy the subtree. But you really should prefer smart pointers to using raw pointers. As was mentioned elsewhere, C++ is not a garbage collected language. You need to manage your memory manually. You are leaking memory like it's 1996.
• You are never default constructing a TNode so you can easily remove that constructor. Doing so means you should make the other one explicit to avoid accidental conversions.
• C++, as opposed to Java has pass-by-value semantics so the TNode constructor will always create a copy of the template argument. If E is a complicated type that handles memory this may not be what you want. For PODs it doesn't matter. You should either pass by const reference const T& or use move semantics which I think is better suited here.

So fixing this up:

template<class T>
struct Node{
    T m_value;
    Node* m_leftChild = nullptr;
    Node* m_rightChild = nullptr;

    explicit Node(T value)
      : m_value(std::move(value))
    {}

    ~Node(){
        delete m_leftChild;
        delete m_rightChild;
    }
};

Naming

Looking at BTree I would prefer the name BinaryTree as it's more descriptive.

Design

I would much prefer a design where the BTree class doesn't expose its internal data structure but rather has member functions to manipulate and traverse the tree. This is a big rewrite so I will not do it here.

In any way, objects in C++ should be constructed as close as possible to their final state, as such your create_tree method should actually be a constructor to BTree. The syntax for adding children is a bit weird, why should I have to know where to place it? It's a binary tree, I would use a class for a binary tree to avoid having to do all this logic. You should simply have a addChild(const E& value) method instead of the intaddLeftChild etc.

public at the top.

It's common to have the public section of your class at the top because this is what your client will likely be interested in, instead of forcing them to scroll through the implementation details.

More memory leaks

You need to have a destructor on BTree to remove the root node when you're done.

Use bool

Also in C++ we have a dedicated boolean data type bool, prefer to use this over returning 1/-1 in an int.

So the signature for your BTree class should be something like this:

template<class T>
class BinaryTree{
public:
    BinaryTree(const T* const arr, int len);
    ~BinaryTree();

    void addChild(const T& value);
    void printTree();
    
    bool contains(const T& value);
   
    ... and more

private:
    struct Node{
        ... implementation here
    };

    Node* m_root = nullptr;
};

Answer 2

Main points to improve:

• Memory leaks: C++ is not garbage collected. Every new must be deleted at some point. This is one of the reasons why C++ has destructors, so that we can perform this and other kinds of cleanup. In modern C++, smart pointers and standard containers are preferable, over manual memory management, since forgetting to delete a pointer is a very easy to make mistake, thus manual memory management being a major source of bugs and memory leaks.

• Unusual data initialization style in constructors:

  TNode<E>(){
      this->value = NULL;
      this->leftChild = NULL;
      this->rightChild = NULL;
  }
  

  The following is the correct way to initialize members. You should use the constructor initialization list. Also, prefixing the variables with a this-> in something we rarely do in C++:

  TNode()
      : value(NULL)
      , leftChild(NULL)
      , rightChild(NULL)
  { }
  

Other tidbits:

• Inside the body of a template class, such as in TNode, you should omit the template parameter in the name. Writing TNode<E> everywhere is too verbose and unnecessary.

• Template parameter name for types is by convention called T instead of E.

• NULL is deprecated since C++11 in favor of the better nullptr.

• Integer return codes are quite error prone. Returning a bool true or false, when the function has only two possible outcomes, is a lot nicer.

• You didn't follow your camelCase notation in the create_tree() method.

Answer 3

Node should have a destructor the deletes its child nodes.

The createTree signature means you can't build from a dynamic array (build itself is private) or a std::vector for example.

E* elementsToLeft = new E[len];  // array to store the left subtree children
E* elementsToRight = new E[len];  // array to store the right sub tree     children

There are multiple problems with this approach:

You allocate new arrays but then don't delete[] them.

This should be followed by a delete[] elementsToLeft; delete[] elementsToRight; at the end of the function.

You copy the elements repeatedly before they are finally stored in the node. If the assignment is non-trivial then this will be unnecessarily expensive.

Instead you can use the fact that the index of the parent is equal to (i+1)/2 - 1 to hold the created nodes in an array:

TNode<E>** nodes = new TNode<E>*[len];
TNode<E>* root = new TNode<E>(arr[i]);
nodes[0] = root;

for(int i = 1; i< len; i++){
    TNode<E>* parent = nodes[(i+1)/2 - 1]:
    TNode<E>* node = new TNode<E>(arr[i]);
    if(i%2 == 0){
        parent->leftNode = node;
    }else{
        parent->rightNode = node;
    }
    nodes[i] = node;
}
delete[] nodes;

return root;