Share your repls and programming experiences

← Back to all posts
Recursive Trie
j_wut (1)

Recursive Typescript solution for Leetcode #208: https://leetcode.com/problems/implement-trie-prefix-tree/

A trie is a way to check prefixes, and can be used in multiple cases such as autocomplete, spell checking, etc. The main difference between a trie and a regular tree, is that in a tree nodes are independent of their children and parents, while trie nodes are dependent on their parents.

example traversal:
tree: 1 -> 2 -> 3 (we only care about current node so we return 3)
trie: 1 -> 2 -> 3 (we care about parents as well, so we return 123)

My design for a trie node stores a string of length 1 (a character) and a map of children. This allows me to do a recursive search without having to create an additional node class.

Inserting a string:
1. check if a child node with the first character exists
2. create/grab the node (aka nextNode). assign the first character to the value
3. if the string to insert is 1 character in length, set the terminal boolean to demark that it is a complete word
4. add "nextNode" to children of current node
5. if the string has length > 1, call insert on "nextNode" with the string ( drop the first character)
6. repeat 1-5 until you've reached the terminal node

Search/startsWith:
1. Perform a normal tree traversal for each character in the search string
2. Once you've reached the last character of the search string:
a) if Search: return true if there is a node and it's terminal value is set.
b) if startsWith: return true if there is a node

Comments
hotnewtop
DynamicSquid (4629)

Hello, we've unlisted this post as it does not have a proper description. If you update your description to reflect your project, then we'd be happy to review and relist this post for you.

j_wut (1)

@DynamicSquid
do you mean an explanation of how it works?

DynamicSquid (4629)

@j_wut Possibly. Right now, I have no idea what your code is or does. I would actually recommend making a tutorial on the algorithm if you want. However, just posting your LeetCode solutions here isn't allowed.

j_wut (1)

@DynamicSquid added a description of what a trie is, and described the algorithms i used for each method

DynamicSquid (4629)

@j_wut That's much better! As a competitive programmer myself, I find this stuff really interesting. However I rarely see solutions in TS... You normally see C/C++ or Java due to the speed. Why did you chose TS?

j_wut (1)

@DynamicSquid just practicing using random languages and show solutions to friends trying to learn,
So in the future, leetcode answers are okay(?) if I accompany them with a similar/comparable explanation?

DynamicSquid (4629)

@j_wut Yeah, as long as you explain them. And just something to consider - not many people here are interested in competitive coding, so it's probably best to post your solutions somewhere else where you'll get more attention and feedback (you can still use Replit to code though :). Let me know if you have any more questions.

And if you want to show your solution to friends, you can just send them the link.