tries.go

package main

import "fmt"

// AlphabteSize is the number of posible characters in tries
const AlphabteSize = 26

// Node represents the each node in the tries
type Node struct {
	children [AlphabteSize]*Node
	isEnd    bool
}

// Trie represnt the trie pointer to the root node
type Trie struct {
	root *Node
}

// init trie will create new trie
func InitTrie() *Trie {
	result := &Trie{root: &Node{}}
	return result
}

// insert will take in a word and add it to the trie
func (t *Trie) Insert(w string) {
	wordlen := len(w)
	currentNode := t.root

	for i := 0; i < wordlen; i++ {
		charIndex := w[i] - 'a'

		if currentNode.children[charIndex] == nil {
			currentNode.children[charIndex] = &Node{}
		}

		currentNode = currentNode.children[charIndex]
	}

	currentNode.isEnd = true
}

// search method wil take the word and return true if the word is in the trie
func (t *Trie) Search(w string) bool {
	wordlen := len(w)
	currentNode := t.root

	for i := 0; i < wordlen; i++ {
		charIndex := w[i] - 'a'

		if currentNode.children[charIndex] == nil {
			currentNode.children[charIndex] = &Node{}
		}

		currentNode = currentNode.children[charIndex]
	}

	if currentNode.isEnd == true {
		return true
	}

	return false
}

func main() {
	myTrie := InitTrie()

	myTrie.Insert("sagar")
	myTrie.Insert("balala")
	myTrie.Insert("aragon")
	myTrie.Insert("jamuna")
	myTrie.Insert("evaly")

	fmt.Println(myTrie.Search("sagar"))
	fmt.Println(myTrie.root)

}