C++11 : simple Tree implementation

Question

I have created a C++11 implementation of a simple Tree for an online code challenge,

I'd like to know how to improve it and how to make my code use less memory :

#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>
#include <sstream>
#include <cassert>

template<class T>
class TreeNode : public std::enable_shared_from_this<TreeNode<T>>
{
    public:

        TreeNode(T data = T(), std::weak_ptr<TreeNode<T>> parent = std::weak_ptr<TreeNode<T>>());

        T getData() const;
        void setData(const T& data);

        TreeNode<T>& addChild(const T& data);
        TreeNode<T>& addChild(std::shared_ptr<TreeNode<T>> ptr);

        void removeChild(size_t indx);
        void removeChild(std::shared_ptr<TreeNode<T>> ptr);

        const std::shared_ptr<TreeNode<T> > findChild(const T& data) const;
        std::shared_ptr<TreeNode<T> > findChild(const T& data);

        std::shared_ptr<const TreeNode<T> > getChild(size_t indx) const;
        std::shared_ptr<TreeNode<T>> getChild(size_t indx);

        const std::weak_ptr<TreeNode<T>> getParent() const;
        std::weak_ptr<TreeNode<T>> getParent();

        void changeParent(std::weak_ptr<TreeNode<T>> parent);

        bool hasChild(const T& data) const
        {
            return findChild(data) != nullptr;
        }

        size_t getNumChildren() const;

        void print() const;

    private:
        T m_data {};
        std::weak_ptr<TreeNode<T>> m_parent { nullptr };
        std::vector<std::shared_ptr<TreeNode<T>>> m_children {};

};

template <class T>
void TreeNode<T>::changeParent(std::weak_ptr<TreeNode<T>> parent)
{
    parent.lock()->addChild(this->shared_from_this());
    m_parent.lock()->removeChild(this->shared_from_this());
    m_parent = parent;
}

template<class T>
TreeNode<T>::TreeNode(T data, std::weak_ptr<TreeNode<T>> parent) : m_parent(parent)
{
    m_data = data;
}

template<class T>
T TreeNode<T>::getData() const
{
    return m_data;
}

template<class T>
void TreeNode<T>::setData(const T& data)
{
    m_data = data;
}

template<class T>
TreeNode<T>& TreeNode<T>::addChild(const T& data)
{
    m_children.push_back(std::make_shared<TreeNode<T>>(data, this->shared_from_this()));
    return *m_children.back();
}

template<class T>
TreeNode<T>& TreeNode<T>::addChild(std::shared_ptr<TreeNode<T>> ptr)
{
    m_children.push_back(ptr);
    return *m_children.back();
}

template<class T>
void TreeNode<T>::removeChild(size_t indx)
{
    m_children.erase(m_children.begin() + indx);
}
template<class T>
void TreeNode<T>::removeChild(std::shared_ptr<TreeNode<T>> ptr)
{
    m_children.erase(std::remove(m_children.begin(), m_children.end(), ptr), m_children.end());
}

template<class T>
const std::shared_ptr<TreeNode<T>> TreeNode<T>::findChild(const T& data) const
{
    for (size_t i { 0 }; i < m_children.size(); ++i)
    {
        if(m_children[i]->getData() == data)
        {
            return m_children[i];
        }
        auto find_child = m_children[i]->findChild(data);
        if (find_child != nullptr)
        {
            return find_child;
        }
    }
    return nullptr;
}

template<class T>
std::shared_ptr<TreeNode<T>> TreeNode<T>::findChild(const T& data)
{
    for (size_t i { 0 }; i < m_children.size(); ++i)
    {
        if(m_children[i]->getData() == data)
        {
            return m_children[i];
        }
        auto find_child = m_children[i]->findChild(data);
        if (find_child != nullptr)
        {
            return find_child;
        }
    }
    return nullptr;
}

template<class T>
std::shared_ptr<const TreeNode<T>> TreeNode<T>::getChild(size_t indx) const
{
    assert(indx < m_children.size());
    return m_children[indx];
}

template<class T>
std::shared_ptr<TreeNode<T> > TreeNode<T>::getChild(size_t indx)
{
    assert(indx < m_children.size());
    return m_children[indx];
}

template<class T>
const std::weak_ptr<TreeNode<T> > TreeNode<T>::getParent() const
{
    return m_parent;
}

template<class T>
std::weak_ptr<TreeNode<T>> TreeNode<T>::getParent()
{
    return m_parent;
}


template<class T>
size_t TreeNode<T>::getNumChildren() const
{
    return m_children.size();
}

template<class T>
void TreeNode<T>::print() const
{
    std::cout << m_data << " ";
    if (!m_children.empty())
    {
        std::cout << "(";
        for (const auto& child : m_children)
        {
            child->print();
        }
        std::cout << ")";
    }
}

Test snippet online on Coliru

Thank you in advance for your advice !

Answer 1

Encapsulation:

My first question is why are you exposing TreeNode? Would the class that implemented a tree not be represented by Tree class? The TreeNode is an internal data structure that is completely private to the tree.

Interface

My second question is what are you trying to achieve with the tree. What you are trying to achieve defines your public interface to the tree. Currently your public interface to the tree is the TreeNode which allows a user to directly manipulate the tree. This is not a good interface. User of your tree don't want to maintain a tree (that is why they are using your class so your class can maintain the tree and they don't need to worry about it). So what is your tree going to be used for, once you answer that you can define the user interface to the tree.

Implementation

Why are you using shared_ptr. Is there really going to be shared ownership of nodes? A tree has a very well defined structure and there is no sharing of nodes each node has children (that are not shared but are owned) and a parent (which is shared but not owned).

So there is no need for shared pointers in the tree.

Are you exposing the TreeNode to the user of the class? That breaks encapsulation (exposing internal details of the tree). So that's not a good idea. Also your need to use std::weak_ptr is a result of sharing the structure externally (exposing implementation details). If you don't allow accesses to the internal structure you don't need to track if a node has references after it is deleted.

So at worst these pointers should be unique_ptr; but personally I would make them all simple pointers (as long as you wrap up the interface and hide the TreeNode from external users).

Code Review

Copy Issues (Move?)

Currently your tree is not copyable or movable.

Copy I think is an issue.

TreeNode   root;
// build a tree here.

TreeNode   extra(root);
// Here extra has all the same shared pointers as root.
// If you modify root directly (by removing or adding a child)
// this is not reflected in extra.
//
// But if you modify the tree below the root node
// i.e. add/remove a node from a child of root then this is reflected
// in extra.

I am not sure this is a good idea.
A tree is an object that should be self contained (all the nodes are part of the tree). If two objects refer to the same tree then changing one should affect the other in exactly the same way.

Move only becomes an issue when you start encapsulating the tree as an object unto-itself.

Adding values.

You currently only support copying T objects into the tree. You may want to support both Move and Build In Place.

   void setData(T&& data);        // Move set
   template<typename... Args>
   vois setData(Args..&& values); // Build in place.

Printing Idioms in C++

I would change the print() to take a stream as a parameter (rather than default to std::cout. Then I would add operator<< so you can rint it using normal C++ idioms.

 void print(std::ostream& = std::cout) const;
 friend std::ostream& operator<<(std::ostream& str, TreeNode const& data)
 {
     data.print(str);
     return str;
 }