C++ Implement the Node Count in Trie

Question

I have below code and i need help to do node count to below codes! Anyone can help me to write that function? I have already words count, but need s help in the Node count!

// C++ implementation to count words in a trie 
#include <bits/stdc++.h> 
using namespace std; 

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 

// Alphabet size (# of symbols) 
#define ALPHABET_SIZE (26) 

// Converts key current character into index 
// use only 'a' through 'z' and lower case 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

// Trie node 
struct TrieNode 
{ 
    struct TrieNode *children[ALPHABET_SIZE]; 

    // isLeaf is true if the node represents 
    // end of a word 
    bool isLeaf; 
}; 

// Returns new trie node (initialized to NULLs) 
struct TrieNode *getNode(void) 
{ 
    struct TrieNode *pNode = new TrieNode; 
        pNode->isLeaf = false; 

    for (int i = 0; i < ALPHABET_SIZE; i++) 
        pNode->children[i] = NULL;     

    return pNode; 
} 

// If not present, inserts key into trie 
// If the key is prefix of trie node, just 
// marks leaf node 
void insert(struct TrieNode *root, const char *key) 
{ 
    int length = strlen(key); 

    struct TrieNode *pCrawl = root; 

    for (int level = 0; level < length; level++) 
    { 
        int index = CHAR_TO_INDEX(key[level]); 
        if (!pCrawl->children[index]) 
            pCrawl->children[index] = getNode(); 

        pCrawl = pCrawl->children[index]; 
    } 

    // mark last node as leaf 
    pCrawl->isLeaf = true; 
} 

// Function to count number of words 
int wordCount(struct TrieNode *root) 
{ 
    int result = 0; 

    // Leaf denotes end of a word 
    if (root -> isLeaf) 
        result++; 

    for (int i = 0; i < ALPHABET_SIZE; i++)     
      if (root -> children[i]) 
         result += wordCount(root -> children[i]); 

    return result;    
} 

// Driver 
int main() 
{ 
    // Input keys (use only 'a' through 'z'  
    // and lower case) 
    char keys[][8] = {"the", "a", "there", "answer",  
                     "any", "by", "bye", "their"}; 


    struct TrieNode *root = getNode(); 

    // Construct Trie 
    for (int i = 0; i < ARRAY_SIZE(keys); i++) 
        insert(root, keys[i]); 

    cout << wordCount(root); 

    return 0; 
}

Unrelated: [Do not use `#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [avoid `using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Using the two together magnifies each other's worst effects, turning the global namespace into a minefield of identifiers, many of which you probably don't even know exist, that now must be avoided. — user4581301, Oct 21 '19 at 19:31
Unrelated: if your compiler is up to date you can replace `#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])` with [`std::size`](https://en.cppreference.com/w/cpp/iterator/size). — user4581301, Oct 21 '19 at 19:33
Unrelated: Prefer a function to the `CHAR_TO_INDEX` macro. The compiler will likely inline it for you so you'll see no performance difference. — user4581301, Oct 21 '19 at 19:36
Please expand on what is meant by node count. Sometimes the act of describing intent shakes what must be done to get the intended behaviour loose from the dark recesses of the brain. And if not, we are in better position to help you because now we know exactly what it is that you need. — user4581301, Oct 21 '19 at 19:40
That could be as simple as incrementing a counter every time you construct a `TrieNode`. Under what circumstances is a node to be considered for the count? — user4581301, Oct 21 '19 at 19:50

score 0 · Answer 1 · answered Oct 22 '19 at 03:54

You can do a simple inorder traversal of the tree.

int inorderTraversal(TrieNode* pNode)
{
    if (!pNode)
        return 0;

    int count = 0;
    for (int i = 0; i < ALPHABET_SIZE; ++i)
        count += inorderTraversal(pNode->children[i]);

    return count + 1;
}

C++ Implement the Node Count in Trie

1 Answers1