Design of a N-ary tree A friend of mine and I recently started a project and at this moment we are writing a common library. He began writing an N-ary three and he is convinced that he has the best design with which I am not agree.

I want to convince him, that his design of the N-ary Tree is very bad, and with this design we will face problems. Due to lack of experience in complex projects from my side -- I can't convince him with my arguments. 

Here is the current design and implementation:

template &lt;typename T&gt;
class Tree {
private:
    T data;
    vector&lt; Tree&lt;T&gt; &gt; successors;

public:
    Tree(T x) {
      data = x;
    }

    T root() {
        return data;
    }
    vector&lt; Tree&lt;T&gt; &gt; succ() {
        return successors;
    }
    void addChild(Tree&lt;T&gt; t) {
        successors.push_back(t);
    }
    void member(T element) {
        if (element == data)
            return true;
        for (int i = 0; i &lt; successors.size(); i++) {
            if(successors[i].member(element)) {
                return true;
            }
        }
        return false;
    }
    void fromRightParentToLeft() {
        if (successors.empty()) {
            cout &lt;&lt; data &lt;&lt; "\n";
            return;
        }
        if (successors.size() == 1) {
            successors[0].fromRightParentToLeft();
            cout &lt;&lt; data &lt;&lt; "\n";
        }
        else {
          for (int i = succ().size(); i &gt; 1; i--) {
            succ()[i-1].fromRightParentToLeft();
          }

          cout &lt;&lt; data &lt;&lt; "\n";
          succ()[0].fromRightParentToLeft();
        }
    }
};


So far I can see few problems:


We will face problem when he will implement a method for node deletion, because it is somehow wrong a node to have the ability to delete itself.
He traverses the tree in a inorder-ish manner, which is pointless when dealing with general N-ary trees.


Can someone point other potential traps with this approach?

The tree must meet the following requirements:


Inteface: node addition, node deletion, search for a particular node, basic tree traversal.
Other: It should be: easily maintainable, with fast performance.


In the general case the tree will have ~10k nodes, which will contain integers.
Some things:

By definition, an N-ary tree is a tree where any node must have no more than N children. However, you never allow the user to define that N, and nowhere do you specify the invariant that for any node, said node must have at most N children. Your tree is not an N-ary tree, it's just a "tree" (with an arbitrary number of children per node).

You're returning bool values in void member(T).

You should decouple traversal from the tree itself. Instead of thinking about traversal like tree.traverse() you should think like traverse(tree).

Reason: to separate and clear up responsibilities. A data structure holds data and nothing else. If you implement traversal behavior inside the tree, the user implementing his own would break any sort of consistency, unless he modifies the structure itself or extends it, which is not exactly desired in this kind of situations (class MySpecialPostOrderTraversalTree : Tree). Furthermore, separating the behavior from the data structure leaves room for other extensions (e.g. a generic traversal algorithm that works on your tree, and on some other kinds of trees, defined by your user).

You should definitely remove the console output from your tree, even if you leave traversal there. At least, you should allow your user to specify a method to call for each visited node. If he wants to print the content of the nodes, he can do it himself. You don't want to give someone a tree that randomly starts to print out stuff to stdout. Also see the concept of mapping functions over collections.

You keep working with values. For example, succ() returns a copy of the vector of children. On large trees this will have a negative effect, constantly copying vectors of elements which contain vectors of elements (and so on) is not exactly a good idea. Look into pointers, and base your tree on them. Start with std::unique_ptr and std::shared_ptr, don't use naked pointers.

See janos's answer for naming suggestions that I feel there's no need to duplicate here :)