Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Introduction to Trie

Introduction to Trie

A Trie, short for retrieval, is a specialized tree-based data structure primarily used for efficient storing, searching, and retrieval of strings over a given alphabet. It excels in scenarios where a large collection of strings needs to be managed and pattern-matching operations need to be performed with optimal efficiency.

Defining a Trie

A Trie, often referred to as a prefix tree, is constructed to represent a set of strings where each node in the tree corresponds to a single character of a string

.....

.....

.....

Like the course? Get enrolled and start learning!
senthil kumar

senthil kumar

· 2 years ago

In case of integer, we just need to check the value of the node with the search value, it will be 0(1) operations.

Where else in string, most of the language will compare each character to character in the default "==" or equal methods . Hence on each step we will compare the whole string ( by one by one character)

[ Explanation from Chat GPT]

Consider a binary search tree (BST) with the following string keys: "apple", "banana", "cherry", "date", "elderberry". The BST might look something like this:

    banana
   /      \
apple    elderberry
   \      /       \
 cherry date

Now, let's say we want to search for the key "date". Here's how the search would proceed:

  1. Start at the root ("banana"). "date" is greater than "banana", so go right.
  2. Now we're at "el
senthil kumar

senthil kumar

· 2 years ago

As we are using array datatype for children, its length is always constraint as the size is defined during initialization.

So the below code to check the presence of children for a node will always return 26 irrespective whether there is actual value or null)

return current.children.length == 0; // Return true if no children exist

We Should use below code instead



 for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                return true;
            }
        }
        return false;
Show 1 reply
senthil kumar

senthil kumar

· 2 years ago

Due to involvement of recursion logic , the space complexity can grow up to 0(m) as we need to store all values in recursion call stack.

M

matthew.carnahan1

· 2 years ago

Imagine a trie that houses 2 words:

  1. car
  2. carton

Is the following trie correct:

Root - c - a - r - t - o - n

The nodes for 'r' and 'n' both have isEndOfWord = True, and the rest have isEndOfWord = False.

Show 1 reply