patterncppMinor

Writing out a tree of Tnodes with words as values in alphabetical order

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

orderalphabeticalwithwordswritingvaluestnodesouttree

Problem

I'm doing this:

Consider:

struct Tnode {
    string word;
    int count;
    Tnode* left;
    Tnode* right;
};

Write a function for entering new words into a tree of Tnodes. Write a
function to write out a tree of Tnodes. Write a function to write out
a tree of Tnodes with the words in alphabetical order. Modify Tnode so
that it stores (only) a pointer to an arbitrarily long word stored as
an array of characters on free store using new. Modify the functions
to use the new definition of Tnode.

Source

Here is my code for the first part ("write a function to write out a tree of Tnodes with the words in alphabetical order"). Please review this.

Note: I know I only have to write a function, but I'm interested in creating a class. Now I'm not sure if this is good code.

```
struct Tnode {
std::string word;
int count; //I'm not sure what's this for. I assume it's for counting nodes.
Tnode* left;
Tnode* right;
};

class TreeNode {
Tnode* node;

Tnode add(Tnode n, const std::string& word) {
if (n == nullptr) {
n = new Tnode{word};
} else if (word word) {
n->left = add(n->left, word);
} else if (word > n->word) {
n->right = add(n->right, word);
} else {
n->word = word;
}
//I have to always check for nullptr because I found out dereferencing a nullptr causes undefined behavior. And I have to asign n->count back to 1 because I notice it keeps adding.
n->count = 1;
if (n->left != nullptr) {
n->count += n->left->count;
}
if (n->right != nullptr) {
n->count += n->right->count;
}
return n;
}

void traverse(Tnode* t) { //for testing purposes
if (t == nullptr) {
return;
}
std::cout word left);
traverse(t->right);
}

void destroy_all(Tnode* t) { //I can't think of a better way to destroy all

Solution

Improvements / details:

Your naming is a bit odd. Tnode is not a very descriptive name. TreeNode seems out of context, as the type is actually the tree itself, not a node.

I suggest renaming TreeNode to just Tree and Tnode to TreeNode instead.

That count parameter seem to be the child count of a given node. It can be used to determine the height of the tree. It is not implemented properly for this purpose though.

I prefer placing private methods and data at the end of the class declaration. Public data and methods should appear at the top, as this is what users of the interface care about when reading the file. Also, it is better to separate the class in declaration and definition. The declaration usually goes in a header file (.h/.hpp).

Wouldn't be a bad idea renaming the recursive helper methods of the tree to make the use of recursion more explicit. You could append _recursive to the name. E.g.: traverse() => traverse_recursive().

Tnode should have a formal constructor to properly initialize its data.

Refactored code:

I took the liberty of applying these changes to your code. Following is the result:

// tree.h:

struct TreeNode {

    std::string word;
    int numChildren;

    TreeNode* left;
    TreeNode* right;

    TreeNode(const std::string& word)
        : word(word), numChildren(0), left(nullptr), right(nullptr) { }
};

class Tree {

public:

    Tree();
    Tree(const std::string& word);

    void add(const std::string& word);
    void traverse();
    int get_num_nodes() const;

    ~Tree();

private:

    TreeNode* add_recursive(TreeNode* n, const std::string& word);
    void traverse_recursive(TreeNode* n);
    void destroy_recursive(TreeNode* n);

    TreeNode * root;
};

// tree.cpp:

Tree::Tree()
    : root(nullptr) { }

Tree::Tree(const std::string& word)
    : root(new TreeNode(word)) { }

void Tree::add(const std::string& word) {
    root = add_recursive(root, word);
}

void Tree::traverse() {
    traverse_recursive(root);
}

int Tree::get_num_nodes() const {
    return root->numChildren + 1; // +1 to count the root as a node
}

Tree::~Tree() {
    destroy_recursive(root);
}

TreeNode* Tree::add_recursive(TreeNode* n, const std::string& word) {
    if (n == nullptr) {
        n = new TreeNode(word);
    } else if (word word) {
        n->left = add_recursive(n->left, word);
        n->numChildren++;
    } else if (word > n->word) {
        n->right = add_recursive(n->right, word);
        n->numChildren++;
    } else {
        n->word = word;
    }

    return n;
}

void Tree::traverse_recursive(TreeNode* n) {
    if (n == nullptr) {
        return;
    }

    // Extended printing to visualize more info:
    std::cout  " word numChildren;
    if (n->left != nullptr) {
        std::cout left->word;
    }
    if (n->right != nullptr) {
        std::cout right->word;
    }
    std::cout left);
    traverse_recursive(n->right);
}

void Tree::destroy_recursive(TreeNode* n) {
    if (n == nullptr) {
        return;
    }
    destroy_recursive(n->left);
    destroy_recursive(n->right);
    delete n;
}

// main.cpp:

int main()
{
    Tree tree;

    tree.add("hello");
    tree.add("C++  ");
    tree.add("world");
    tree.add("foo  ");
    tree.add("bar  ");
    tree.add("baz  ");

    tree.traverse();

    std::cout << "num nodes: " << tree.get_num_nodes() << std::end; // prints "num nodes: 6"
}

Code Snippets

// tree.h:

struct TreeNode {

    std::string word;
    int numChildren;

    TreeNode* left;
    TreeNode* right;

    TreeNode(const std::string& word)
        : word(word), numChildren(0), left(nullptr), right(nullptr) { }
};

class Tree {

public:

    Tree();
    Tree(const std::string& word);

    void add(const std::string& word);
    void traverse();
    int get_num_nodes() const;

    ~Tree();

private:

    TreeNode* add_recursive(TreeNode* n, const std::string& word);
    void traverse_recursive(TreeNode* n);
    void destroy_recursive(TreeNode* n);

    TreeNode * root;
};

// tree.cpp:

Tree::Tree()
    : root(nullptr) { }

Tree::Tree(const std::string& word)
    : root(new TreeNode(word)) { }

void Tree::add(const std::string& word) {
    root = add_recursive(root, word);
}

void Tree::traverse() {
    traverse_recursive(root);
}

int Tree::get_num_nodes() const {
    return root->numChildren + 1; // +1 to count the root as a node
}

Tree::~Tree() {
    destroy_recursive(root);
}

TreeNode* Tree::add_recursive(TreeNode* n, const std::string& word) {
    if (n == nullptr) {
        n = new TreeNode(word);
    } else if (word < n->word) {
        n->left = add_recursive(n->left, word);
        n->numChildren++;
    } else if (word > n->word) {
        n->right = add_recursive(n->right, word);
        n->numChildren++;
    } else {
        n->word = word;
    }

    return n;
}

void Tree::traverse_recursive(TreeNode* n) {
    if (n == nullptr) {
        return;
    }

    // Extended printing to visualize more info:
    std::cout << "Node => " << n->word << ", numChildren: " << n->numChildren;
    if (n->left != nullptr) {
        std::cout << ", left: "  << n->left->word;
    }
    if (n->right != nullptr) {
        std::cout << ", right: " << n->right->word;
    }
    std::cout << "\n";

    traverse_recursive(n->left);
    traverse_recursive(n->right);
}

void Tree::destroy_recursive(TreeNode* n) {
    if (n == nullptr) {
        return;
    }
    destroy_recursive(n->left);
    destroy_recursive(n->right);
    delete n;
}

// main.cpp:

int main()
{
    Tree tree;

    tree.add("hello");
    tree.add("C++  ");
    tree.add("world");
    tree.add("foo  ");
    tree.add("bar  ");
    tree.add("baz  ");

    tree.traverse();

    std::cout << "num nodes: " << tree.get_num_nodes() << std::end; // prints "num nodes: 6"
}

Context

StackExchange Code Review Q#66560, answer score: 3

Revisions (0)

No revisions yet.