You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in debugging TRIE delete function

I'm trying to implement trie data structure but I'm facing difficulty in implementing the delete function. I don't know why the delete operator is not working properly while de-allocating memory for child nodes. Can someone please help in finding the mistake!!

code link

asked 16 Mar '18, 23:24

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

edited 19 Mar '18, 23:36


include <bits stdc++.h="">

using namespace std;

const int ALPHABET_SIZE = 26;

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

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

};

// Returns new trie node (initialized to NULLs) struct TrieNode getNode(void) { struct TrieNode pNode = new TrieNode;

pNode->isEndOfWord = 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, string key) { struct TrieNode pCrawl = root;

for (int i = 0; i < key.length(); i++)
{
    int index = key[i] - 'a';
    if (!pCrawl->children[index])
        pCrawl->children[index] = getNode();

    pCrawl = pCrawl->children[index];
}

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

}

// Returns true if key presents in trie, else // false bool search(struct TrieNode root, string key) { struct TrieNode pCrawl = root;

for (int i = 0; i < key.length(); i++)
{
    int index = key[i] - 'a';
    if (!pCrawl->children[index])
        return false;

    pCrawl = pCrawl->children[index];
}

return (pCrawl != NULL && pCrawl->isEndOfWord);

}

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

struct TrieNode *root = getNode();

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

// Search for different keys
search(root, "the")? cout << "Yes\n" :
                     cout << "No\n";
search(root, "these")? cout << "Yes\n" :
                       cout << "No\n";
return 0;

}

link

answered 20 Mar '18, 16:55

gyanendra371's gravatar image

3★gyanendra371
2936
accept rate: 33%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×186
×56
×7

question asked: 16 Mar '18, 23:24

question was seen: 223 times

last updated: 20 Mar '18, 16:55