I'm reviewing bfs and dfs concepts and recently wrote this search method for a Trie tree. I believe it is bfs because we're searching each level starting from the root if the next value exists. I'm not sure what implementing dfs would look like in a problem like this. I could be completely wrong though.
class TrieTree {
constructor() {
this.root = new TreeNode();
}
insert(word) {
let currentNode = this.root;
for (let char of word) {
if (currentNode.children.has(char)) {
currentNode = currentNode.children.get(char);
continue;
} else {
currentNode.children.set(char, new TreeNode(char));
currentNode = currentNode.children.get(char);
}
}
currentNode.isWord = true;
}
//I'm not sure if this should be called bfs or dfs
bfs(searchTerm) {
let currentNode = this.root;
for (let char of searchTerm) {
if (currentNode.children.has(char)) {
currentNode = currentNode.children.get(char);
} else {
return false;
}
}
return (currentNode.isWord)
}
}
class TreeNode {
constructor(val) {
this.data = val;
this.children = new Map(); //collection of nodes in TS we would use TreeNode[];
this.isWord = false;
}
}
let tree = new TrieTree();
tree.insert("hello");
tree.insert("bucky");
tree.insert("hell");
console.log(tree.bfs("bucky"));
It is neither. You're not iterating the whole tree, which can be done in bfs or dfs manner. You're just accessing the element in the position where you expect it in your trie. This query operation is typically called find, get or has.
Given
tree.insert("helios");
tree.insert("hello");
tree.insert("helipad");
Your data structure looks like this:
h
|
e
|
l
/ \
i l
/ \ \
o p o
| |
s a
|
d
However, since each level is implemented as a map and the search is using Map#has/Map#get there is no search over the entire space. When looking up "helipad", the algorithm would never consider the first branching after h -> e -> l it would directly jump to the i part and discard the l branch. Similarly after h -> e -> l -> i it will not consider the o as possible path but directly continue with p. That is not how breadth first search works.
It is also not how depth first search works, since if it was it would first try h -> e -> l -> i -> o -> s then backtrack to i and attempt h -> e -> l -> i -> p -> a -> d.