Design of tree data structure

Question

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?

Answer 1

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)