Trie: Second Implementation in Groovy

This is another version of Trie implementation in my previous post. The new one comes with a flag to identify a complete word.

	class Node {
	/*data to be save*/
	def data
	/*child nodes of this node*/
	def children = [:]
	/*any key finshied in this node? (end of a word)*/
	def flag = false
	}
	class Trie {
	/*Root node with empty data - edited*/
	def root = new Node(data:'')
	def insert(key) {
	def node = root
	key.each {
	/*find the relevant child node*/
	def child = node.children[it]
	/*if child does not exist, creates it*/
	if (child == null) {
	child = node.children[it] = new Node(data:it)
	}
	node = child
	}
	/*flag the last node as end of this word*/
	node.flag = true
	}
	def search(key) {
	def node = root
	def x = key.find {
	node = node.children[it]
	/*if the child does not exist, key does not exist in trie*/
	node == null
	}
	/*check if the chain of characters exists AND its a complete word (flag == true)*/
	return x == null && node.flag
	}
	def disply() {
	print(root, '')
	}
	private print(node, prefix) {
	/*if its a complete word, print it*/
	if (node.flag) {
	println "${prefix}${node.data}"
	}
	/*visit children, to find rest of words*/
	node.children.values().each {
	print(it, prefix + node.data)
	}
	}
	}
	def t = new Trie()
	t.insert("trie")
	t.insert("tree")
	t.insert("i")
	t.insert("it")
	t.insert("ite")
	assert false == t.search("t")
	assert false == t.search("tr")
	assert false == t.search("tri")
	assert true == t.search("trie")
	assert false == t.search("tre")
	assert true == t.search("tree")
	assert true == t.search("i")
	assert true == t.search("it")
	assert true == t.search("ite")
	assert false == t.search("triex")
	assert false == t.search("treexx")
	assert false == t.search("ix")
	t.disply()

view raw gistfile1.groovy hosted with ❤ by GitHub