Insert and Search in a Trie

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ALPHABET 26

// One trie node: 26 child links and an end flag
struct Node {
    struct Node *children[ALPHABET];
    bool isEnd;
};

// Make a fresh empty node
struct Node *newNode() {
    struct Node *n = malloc(sizeof(struct Node));
    for (int i = 0; i < ALPHABET; i++) n->children[i] = NULL;
    n->isEnd = false;
    return n;
}

// Walk the word and build any missing path, then mark the end
void insert(struct Node *root, const char *word) {
    struct Node *cur = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int idx = word[i] - 'a';
        if (cur->children[idx] == NULL)
            cur->children[idx] = newNode();
        cur = cur->children[idx];
    }
    cur->isEnd = true;
}

// Walk the path; return the end flag of the last node
bool search(struct Node *root, const char *word) {
    struct Node *cur = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int idx = word[i] - 'a';
        if (cur->children[idx] == NULL) return false;
        cur = cur->children[idx];
    }
    return cur->isEnd;
}

// Walk the path; true if it exists, ignore the end flag
bool startsWith(struct Node *root, const char *prefix) {
    struct Node *cur = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int idx = prefix[i] - 'a';
        if (cur->children[idx] == NULL) return false;
        cur = cur->children[idx];
    }
    return true;
}

int main() {
    struct Node *root = newNode();
    insert(root, "car");
    insert(root, "card");
    insert(root, "cat");

    printf("search car  : %s\n", search(root, "car") ? "true" : "false");
    printf("search care : %s\n", search(root, "care") ? "true" : "false");
    printf("startsWith ca : %s\n", startsWith(root, "ca") ? "true" : "false");
    printf("startsWith do : %s\n", startsWith(root, "do") ? "true" : "false");
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

// One trie node: a map of children and an end flag
struct Node {
    unordered_map<char, Node*> children;
    bool isEnd = false;
};

// Walk the word and build any missing path, then mark the end
void insert(Node *root, const string &word) {
    Node *cur = root;
    for (char ch : word) {
        if (cur->children.find(ch) == cur->children.end())
            cur->children[ch] = new Node();
        cur = cur->children[ch];
    }
    cur->isEnd = true;
}

// Walk the path; return the end flag of the last node
bool search(Node *root, const string &word) {
    Node *cur = root;
    for (char ch : word) {
        if (cur->children.find(ch) == cur->children.end()) return false;
        cur = cur->children[ch];
    }
    return cur->isEnd;
}

// Walk the path; true if it exists, ignore the end flag
bool startsWith(Node *root, const string &prefix) {
    Node *cur = root;
    for (char ch : prefix) {
        if (cur->children.find(ch) == cur->children.end()) return false;
        cur = cur->children[ch];
    }
    return true;
}

int main() {
    Node *root = new Node();
    insert(root, "car");
    insert(root, "card");
    insert(root, "cat");

    cout << "search car  : " << (search(root, "car") ? "true" : "false") << endl;
    cout << "search care : " << (search(root, "care") ? "true" : "false") << endl;
    cout << "startsWith ca : " << (startsWith(root, "ca") ? "true" : "false") << endl;
    cout << "startsWith do : " << (startsWith(root, "do") ? "true" : "false") << endl;
    return 0;
}

import java.util.HashMap;

public class TrieOps {
    // One trie node: a map of children and an end flag
    static class Node {
        HashMap<Character, Node> children = new HashMap<>();
        boolean isEnd = false;
    }

    static Node root = new Node();

    // Walk the word and build any missing path, then mark the end
    static void insert(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) {
            cur.children.putIfAbsent(ch, new Node());
            cur = cur.children.get(ch);
        }
        cur.isEnd = true;
    }

    // Walk the path; return the end flag of the last node
    static boolean search(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) {
            if (!cur.children.containsKey(ch)) return false;
            cur = cur.children.get(ch);
        }
        return cur.isEnd;
    }

    // Walk the path; true if it exists, ignore the end flag
    static boolean startsWith(String prefix) {
        Node cur = root;
        for (char ch : prefix.toCharArray()) {
            if (!cur.children.containsKey(ch)) return false;
            cur = cur.children.get(ch);
        }
        return true;
    }

    public static void main(String[] args) {
        insert("car");
        insert("card");
        insert("cat");

        System.out.println("search car  : " + search("car"));
        System.out.println("search care : " + search("care"));
        System.out.println("startsWith ca : " + startsWith("ca"));
        System.out.println("startsWith do : " + startsWith("do"));
    }
}

class Node:
    # One trie node: a dict of children and an end flag
    def __init__(self):
        self.children = {}
        self.is_end = False


class Trie:
    def __init__(self):
        self.root = Node()

    # Walk the word and build any missing path, then mark the end
    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = Node()
            cur = cur.children[ch]
        cur.is_end = True

    # Walk the path; return the end flag of the last node
    def search(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return cur.is_end

    # Walk the path; true if it exists, ignore the end flag
    def starts_with(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True


trie = Trie()
trie.insert("car")
trie.insert("card")
trie.insert("cat")

print("search car  :", trie.search("car"))
print("search care :", trie.search("care"))
print("startsWith ca :", trie.starts_with("ca"))
print("startsWith do :", trie.starts_with("do"))

class Node {
  // One trie node: a map of children and an end flag
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  // Walk the word and build any missing path, then mark the end
  insert(word) {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch)) cur.children.set(ch, new Node());
      cur = cur.children.get(ch);
    }
    cur.isEnd = true;
  }

  // Walk the path; return the end flag of the last node
  search(word) {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch)) return false;
      cur = cur.children.get(ch);
    }
    return cur.isEnd;
  }

  // Walk the path; true if it exists, ignore the end flag
  startsWith(prefix) {
    let cur = this.root;
    for (const ch of prefix) {
      if (!cur.children.has(ch)) return false;
      cur = cur.children.get(ch);
    }
    return true;
  }
}

const trie = new Trie();
trie.insert("car");
trie.insert("card");
trie.insert("cat");

console.log("search car  :", trie.search("car"));
console.log("search care :", trie.search("care"));
console.log("startsWith ca :", trie.startsWith("ca"));
console.log("startsWith do :", trie.startsWith("do"));