[BUG] Trie deleteString corrupts words sharing prefixes

[sudheerxdev]

Description

Description

Briefly explain the bug in 1-2 lines.

Expected Behavior

deleteString should remove only the specified word while preserving other words that share the same prefix.

Actual Behavior

When deleteString("Hello", 0) is called after inserting both "Hell" and "Hello", the word "Hell" also gets corrupted/deleted.

Steps to Reproduce

1. Insert "Hell" into trie
2. Insert "Hello" into trie
3. Call deleteString("Hello", 0)
4. Try to search("Hell", 0)
5. Result: "Hell" is no longer found (BUG)

Expected Result

"Hell" should still be searchable after deleting "Hello"

Actual Result

Both "Hell" and "Hello" are deleted

Environment

• File: data_structures/trie_tree.cpp
• Function: deleteString()
• Lines: 128-140

Root Cause

Line 125 unconditionally resets child pointer without checking if subtree is truly empty

Suggested Fix

Only prune nodes when they have:

• No children (no active branches)
• AND isEndofWord is false (not a terminal word)

Expected behavior

deleteString should only remove the specified word while preserving all other words in the trie, especially those that share prefixes with the deleted word.

For example, after deleting "Hello", the word "Hell" should remain searchable.

Actual behavior

deleteString unconditionally resets child pointers after recursion, corrupting words that share prefixes.

After deleteString("Hello", 0), calling search("Hell", 0) returns false (incorrect - should return true).

Both words get deleted instead of just "Hello".

Steps to reproduce

1. Create a trie and insert "Hell"
2. Insert "Hello"
3. Verify both search("Hell", 0) and search("Hello", 0) return true
4. Call deleteString("Hello", 0)
5. Call search("Hell", 0)
6. Bug: Returns false (should return true)

Context

This bug affects any application using the trie for prefix-based dictionary operations. Words sharing prefixes cannot be safely managed. The issue is critical for autocomplete systems, spell checkers, and IP routing tables.

Additional information

Root Cause: Line 125 in deleteString() resets child pointer without verifying the subtree is empty:

• Missing check: if (!arr[j]->isEndofWord && !arr[j]->hasChildren())

Link to PR: See PR #3135 for proposed fix with regression tests

Verified in: data_structures/trie_tree.cpp (lines 128-140)