A ternary search tree is a trie-like data structure where each node may have up to three children. Here is an example which represents the words code, cob, be, ax, war, and we.

A ternary search tree is a trie-like data structure where each node may have up to three children. Here is an example which represents the words code, cob, be, ax, war, and we.

       c

    /  |  \

   b   o   w

 / |   |   |

a  e   d   a

|    / |   | \ 

x   b  e   r  e  

The tree is structured according to the following rules:

left child nodes link to words lexicographically earlier than the parent prefix

right child nodes link to words lexicographically later than the parent prefix

middle child nodes continue the current word

For instance, since code is the first word inserted in the tree, and cob lexicographically precedes cod, cob is represented as a left child extending from cod.

Implement insertion and search functions for a ternary search tree.

Solution

Python

class TernarySearchTreeNode:
    def __init__(self, char):
        self.char = char
        self.left = None
        self.middle = None
        self.right = None
        self.is_end_of_word = False

class TernarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, root, word):
        if not word:
            return root
        char = word[0]
        if root is None:
            root = TernarySearchTreeNode(char)
        if char < root.char:
            root.left = self.insert(root.left, word)
        elif char > root.char:
            root.right = self.insert(root.right, word)
        else:
            if len(word) > 1:
                root.middle = self.insert(root.middle, word[1:])
            else:
                root.is_end_of_word = True
        return root

    def search(self, root, word):
        if not root or not word:
            return False
        char = word[0]
        if char < root.char:
            return self.search(root.left, word)
        elif char > root.char:
            return self.search(root.right, word)
        else:
            if len(word) == 1:
                return root.is_end_of_word
            return self.search(root.middle, word[1:])

# Usage
tree = TernarySearchTree()
words = ["code", "cob", "be", "ax", "war", "we"]
for word in words:
    tree.root = tree.insert(tree.root, word)

print(tree.search(tree.root, "code"))  # True
print(tree.search(tree.root, "car"))   # False

JAVA

class TSTNode {
    char data;
    TSTNode left, middle, right;
    boolean isEndOfWord;

    TSTNode(char data) {
        this.data = data;
        this.isEndOfWord = false;
    }
}

class TernarySearchTree {
    private TSTNode root;

    public void insert(String word) {
        root = insert(root, word);
    }

    private TSTNode insert(TSTNode node, String word) {
        if (word.isEmpty()) return node;
        char c = word.charAt(0);
        if (node == null) node = new TSTNode(c);
        if (c < node.data) {
            node.left = insert(node.left, word);
        } else if (c > node.data) {
            node.right = insert(node.right, word);
        } else {
            if (word.length() > 1) {
                node.middle = insert(node.middle, word.substring(1));
            } else {
                node.isEndOfWord = true;
            }
        }
        return node;
    }

    public boolean search(String word) {
        return search(root, word);
    }

    private boolean search(TSTNode node, String word) {
        if (node == null || word.isEmpty()) return false;
        char c = word.charAt(0);
        if (c < node.data) {
            return search(node.left, word);
        } else if (c > node.data) {
            return search(node.right, word);
        } else {
            if (word.length() == 1) return node.isEndOfWord;
            return search(node.middle, word.substring(1));
        }
    }

    public static void main(String[] args) {
        TernarySearchTree tst = new TernarySearchTree();
        tst.insert("code");
        tst.insert("cob");
        tst.insert("be");
        tst.insert("ax");
        tst.insert("war");
        tst.insert("we");

        System.out.println(tst.search("code")); // true
        System.out.println(tst.search("car"));  // false
    }
}

JAVASCRIPT

class TSTNode {
    constructor(char) {
        this.char = char;
        this.left = null;
        this.middle = null;
        this.right = null;
        this.isEndOfWord = false;
    }
}

class TernarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(word) {
        this.root = this._insert(this.root, word);
    }

    _insert(node, word) {
        if (!word) return node;
        const char = word[0];
        if (!node) node = new TSTNode(char);
        if (char < node.char) {
            node.left = this._insert(node.left, word);
        } else if (char > node.char) {
            node.right = this._insert(node.right, word);
        } else {
            if (word.length > 1) {
                node.middle = this._insert(node.middle, word.slice(1));
            } else {
                node.isEndOfWord = true;
            }
        }
        return node;
    }

    search(word) {
        return this._search(this.root, word);
    }

    _search(node, word) {
        if (!node || !word) return false;
        const char = word[0];
        if (char < node.char) {
            return this._search(node.left, word);
        } else if (char > node.char) {
            return this._search(node.right, word);
        } else {
            if (word.length === 1) return node.isEndOfWord;
            return this._search(node.middle, word.slice(1));
        }
    }
}

// Usage
const tst = new TernarySearchTree();
const words = ["code", "cob", "be", "ax", "war", "we"];
words.forEach((word) => tst.insert(word));

console.log(tst.search("code")); // true
console.log(tst.search("car"));  // false

Each implementation supports inserting words into the TST and searching for them efficiently.