# Design of tree data structure

I am practicing for technical interviews and I am encountering a lot of problems relating to the tree data structure. I have gone through other posts that discuss about the tree data structure and come up with the class definition and method signatures for the some of the operations as below:

class Tree {
struct Node {
int data;
Node *left;
Node *right;
Node(int d): data(d), left(nullptr), right(nullptr) {}
};
Node *root_;
Tree(Node *r): root_(r) {};
public:
Tree(): root_(nullptr) {};
~Tree();
void deserializeTree(std::string serializedTree);
Tree::Node* deserializeTreeHelper(Tree::Node *root, std::string serializedTree, int *start);
void printTreeHelper(Node *root);
void printTree();
void mirrorTree();
};


Since a lot of operations related to trees can be modeled as recursive functions, with my above class definition, I seem to end up having a method that can be invoked on the tree object and another helper method that does the recursive operation.

My reasoning in having a helper method is because recursive tree operations like the one below needs to return the root of a sub tree and root is of type Tree::Node which is private to the Tree. Hence I can't have the parent method (the method that invokes the recursive helper method) returning Tree::Node.

void
Tree::deserializeTree(std::string serializedTree) {
if (serializedTree.length() <= 0 || serializedTree.substr(0, 1) == std::string("#"))
return;
int start = 0;
root_ = deserializeTreeHelper(root_, serializedTree, &start);
}

Tree::Node*
Tree::deserializeTreeHelper(Node *root, std::string serializedTree, int *start) {
if (*start == serializedTree.length()) return nullptr;
if (serializedTree.substr(*start, 1) == "#") *start = *start + 2;
if (*start >= serializedTree.length()) return nullptr;

std::stringstream ss; ss << serializedTree.substr(*start, 1);
int data; ss >> data;
root = new Node(data);
*start = *start + 1;
root->left = deserializeTreeHelper(root->left, serializedTree, start);
root->right = deserializeTreeHelper(root->right, serializedTree, start);
return root;
}


I want to know if having this kind of operation-operationHelper method combination a good design or is there a better way to design the methods?

I think this is OK, but there are a few things I'd consider changing.

1. Your helpers should be protected or private, since they should only be being called by the non-helper methods.

2. You should consider the const-ness of your methods. e.g. you want void printTree() const.

3. If you're using this pattern a lot, you could consider using a visitor pattern for things that traverse the tree, and a builder style pattern for things that build the tree. This way printTree could be moved outside the class and implemented as something like

void printTree(const Tree& tree) {
tree.visit( TreePrinter() );
}


And similarly the deserializeTree function would be replaced with a constructor like this

Tree tree( TreeBuilderFromString(rep) );

4. It looks like the code reads a balanced (or almost balanced) tree. But since presumably you can build a non-balanced tree, serialization followed by deserialization will not generate the original tree. (Maybe this is expected and OK, but it may surprise someone when they try to use the class)