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?