3
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.