How do I construct a binary tree in a C++ function and return it?

Question

I made a simple binary tree structure in C++:

template <class T>
struct MyBinaryTree {
  T val;
  BinaryTree<T>* left;
  BinaryTree<T>* right;
  BinaryTree<T>(T v, BinaryTree<T>* l, BinaryTree<T>* r)
      : val(v), left(l), right(r) {}
};

I want to write a function that creates a binary tree and returns it. Unfortunately, this structure contains pointers. Hence, if I return a binary tree on a stack, the pointers will become irrelevant.

Is there a way for me to return the binary tree structure?

Just make sure the binary tree manages all its resources, and provide suitable copy constructor, assignment operator, destructor, etc. — juanchopanza, Jun 04 '13 at 04:58
linked list implementation would be better ,with dynamic memory allocation — Arun Killu, Jun 04 '13 at 05:03
Look at the interfaces of binary trees in the standard library, e.g. `std::set` and `std::map`. There are no raw pointers in the interface, users do not have to perform any dynamic memory allocation explicitly, they can be copied, assigned to and clean up their resources when they go out of scope. You can simply create one in a function, return it and not worry about it. The solutions/suggestions involving `new` are directing you towards future pain. — juanchopanza, Jun 04 '13 at 05:10
@juanchopanza This is irrelevant to the OP's question. If `std::set` and `std::map` are implemented as binary trees, they simply have to allocate the nodes dynamically (otherwise they would be tough to move around). Use of `new` *for nodes* is inevitable here (but the tree may be returned by value quickly, using the move semantics from C++11). — Spook, Jun 04 '13 at 05:25
@Spook it is not irrelevant at all. If you want to be able to return objects from a function, you need a type that is safe to copy. Using `new` here is guaranteed to cause problems in the future, it is not a real solution. — juanchopanza, Jun 04 '13 at 05:28
@juanchopanza I don't agree, that it *guarantees* problems in the future, it just requires the programmer to be a lot more careful. If you have a type, which is safe to copy, memory management becomes easier, but at the expense of time and memory performance (especially when returning from a function or method). — Spook, Jun 04 '13 at 05:32
@Spook Nothing it guaranteed. But it is extremely likely. Might as well start typing answers to the follow up questions about memory leaks, double deletes, unexplained modification of data inside one tree after modification of another one... — juanchopanza, Jun 04 '13 at 05:40

score 2 · Accepted Answer · edited May 23 '17 at 12:21

2

As others have noted, you will need to utilize dynamic allocation. When using new, you would typically need to obey the Rule of Three, Four, or Five. This means you would need to make decisions about how destruction, copy construction, assignment, move construction, and move assignment should behave, and implement them. Typically for a container, you want deep copy semantics. Even if you use smart pointers to make destruction simple, you would need to do something more to make copies deep.

However, one doesn't necessarily need to involve new to apply dynamic memory allocation. For example, you could use a list<> to represent left and right instead, and doing it this way gives you deep copy semantics automatically:

template <typename T>
class MyBinaryTree {
    T val_;
    std::list< MyBinaryTree<T> > left_;
    std::list< MyBinaryTree<T> > right_;

    template <typename U>
    friend MyBinaryTree<U> MakeMyBinaryTree (U v,
                                             MyBinaryTree<U> *l = 0,
                                             MyBinaryTree<U> *r = 0) {
        MyBinaryTree<U> t;
        t.val_ = v;
        if (l) t.left_.push_back(*l);
        if (r) t.right_.push_back(*r);
        return t;
    }

public:
    MyBinaryTree<T>* left () { return left_.empty() ? 0 : &*left_.begin(); }
    MyBinaryTree<T>* right () { return right_.empty() ? 0 : &*right_.begin(); }
    T & val () { return val_; }
};

MyBinaryTree<int> make_a_tree ()
{
    MyBinaryTree<int> n1 = MakeMyBinaryTree(1);
    MyBinaryTree<int> n3 = MakeMyBinaryTree(3);
    return MakeMyBinaryTree(2, &n1, &n3);
}

Instead of list<>, you could use Boost.Optional, or if C++14 is available to you, std::optional.

edited May 23 '17 at 12:21

Community

1
1

answered Jun 04 '13 at 05:53

jxh

69,070
8
110
193

I really don't think the lists are necessary here, since they only seem to ever contain up to one element. – juanchopanza Jun 04 '13 at 06:00
@juanchopanza: What would you use instead that would remain rule of 3/4/5 compliant and not involve the `new` operator? – jxh Jun 04 '13 at 06:01
I would use either a smart pointer or an `optional` (`boost` or `std`) object. – juanchopanza Jun 04 '13 at 06:03
The smart pointer woulrd require some form of "deep" copying though. – juanchopanza Jun 04 '13 at 06:09
1

@juanchopanza: I already mentioned smart pointer in the answer, but I added mentions of `optional` at the end of the answer. Thanks. – jxh Jun 04 '13 at 06:11
Wait how does it find MakeMyBinaryTree if that function scope is contained inside MyBinaryTree class? Also wouldn't a proper constructor be a better fit than the MakeMyBinaryTree function? – dchhetri Jun 04 '13 at 15:19
`MakeMyBinaryTree` is a friend function that is just implemented inside the class. It is an ordinary function. I defined a function because your question asked for one. – jxh Jun 04 '13 at 15:25

Spook · Answer 2 · 2013-06-04T05:34:54.903

You created a dynamic container - eg. the one, which is built during the runtime. In case of such structures, you have to allocate them dynamically and use pointer to refer to them. That is:

MyBinaryTree * BuildSimpleTree()
{
    BinaryTree<int> * node1 = new BinaryTree(0, nullptr, nullptr);
    BinaryTree<int> * node2 = new BinaryTree(0, nullptr, nullptr);

    return new MyBinaryTree<int>(0, node1, node 2);
}

MyBinaryTree * tree = BuildSimpleTree();

The reason behind dynamic allocation requirement is that all local statically allocated objects (eg. residing on stack instead of heap) are automatically destroyed, when you leave the function or method. However, for the tree to work properly, all its children (and recursively their children) shall remain alive after returning from function, so they have to be allocated dynamically.

You have to remember though to free all instances of allocated classes. This may be done manually or automatically, recursively - in BinaryTree and MyBinaryTree dtors.

If you are able to compile your code using C++11, there's always an option to use move semantics - you'll be able to return the tree by value and keep the code fast and memory-efficient at the same time. This solution would look like the following:

template <class T>
struct MyBinaryTree 
{
    T val;
    BinaryTree<T>* left;
    BinaryTree<T>* right;
    BinaryTree<T>(T v, BinaryTree<T>* l, BinaryTree<T>* r)
      : val(v), left(l), right(r) 
    {
    }

    BinaryTree<T>(BinaryTree<T> && r)
    {
        val = r.val;
        left = r.left;
        right = r.right;
    }
};

Then, you can return your tree by value (but still building nodes dynamically):

MyBinaryTree BuildTree()
{
     auto left = new BinaryTree<int>(0, nullptr, nullptr);
     auto right = new BinaryTree<int>(0, nullptr, nullptr);
     MyBinaryTree<int> result(0, left, right);
     return result;
}

score 1 · Answer 3 · answered Jun 04 '13 at 05:00

You need to dynamically allocate data. For example to create

  2
 / \
1   3

using your structure you would do the following:

MyBinaryTree<int>* getTestStructure(){
   MyBinaryTree<int> *root = new MyBinaryTree<int>(2);
   MyBinaryTree<int> *leftChild = new MyBinaryTree<int>(1);
   MyBinaryTree<int> *rightChild = new MyBinaryTree<int>(3);
   root.left = leftChild;
   root.right = rightChild;
   return root;
}

How do I construct a binary tree in a C++ function and return it?

3 Answers3