Ternary Search Tree Implementation

Problem

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.

1
2
3
4
5
6
7


       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.

Examples

Example 1

1
2
3
4
5
6
7


Input: 
Insert words: ["code", "cob", "be", "ax", "war", "we"]
Search: "code"
Output: true
Explanation:
After inserting all words, searching for "code" should return true as it exists in the tree.
The word follows the path: c -> o (middle) -> d (middle) -> e (middle, end of word).

Example 2

1
2
3
4
5
6
7


Input:
Insert words: ["code", "cob", "be", "ax", "war", "we"]
Search: "cod"
Output: false
Explanation:
"cod" is a prefix of "code" but not a complete word in the tree.
The path exists (c -> o -> d) but the node at 'd' is not marked as end of word.

Example 3

1
2
3
4
5
6


Input:
Insert words: ["code", "cob", "be", "ax", "war", "we"]
Search: "cob"
Output: true
Explanation:
"cob" should return true. Path: c -> o (middle) -> b (left, because 'b' < 'd').

Example 4

1
2
3
4
5
6


Input:
Insert words: ["test", "tea", "ted", "ten", "i", "in", "inn"]
Search: "te"
Output: false
Explanation:
"te" is a prefix but not a complete word. Need to reach a node marked as end of word.

Example 5

1
2
3
4
5
6
7


Input:
Insert words: ["apple", "app", "application"]
Search: "app"
Output: true
Explanation:
"app" is both a complete word and a prefix of other words.
The node at the second 'p' should be marked as end of word.

Solution

Method 1 - Standard Ternary Search Tree Implementation

Intuition

A ternary search tree combines features of binary search trees and tries. Each node stores a character and has three children: left (for characters lexicographically smaller), middle (for the next character in the current word), and right (for characters lexicographically larger). This structure allows efficient string operations while maintaining sorted order.

Approach

Create a node structure with character, three child pointers, and end-of-word flag
For insertion: traverse the tree comparing characters, going left/right for different characters, middle for same character
Create new nodes as needed and mark the final node as end-of-word
For search: follow the same traversal logic, return true only if we reach end-of-word
Handle edge cases: empty strings, null inputs, and prefix vs complete word distinction

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


class TernarySearchTree {
private:
    struct Node {
        char ch;
        bool isEnd;
        Node* left;
        Node* middle;
        Node* right;
        
        Node(char c) : ch(c), isEnd(false), left(nullptr), middle(nullptr), right(nullptr) {}
    };
    
    Node* root;
    
    Node* insertHelper(Node* node, const string& word, int idx) {
        char ch = word[idx];
        
        if (!node) {
            node = new Node(ch);
        }
        
        if (ch < node->ch) {
            node->left = insertHelper(node->left, word, idx);
        } else if (ch > node->ch) {
            node->right = insertHelper(node->right, word, idx);
        } else {
            if (idx < word.length() - 1) {
                node->middle = insertHelper(node->middle, word, idx + 1);
            } else {
                node->isEnd = true;
            }
        }
        
        return node;
    }
    
    bool searchHelper(Node* node, const string& word, int idx) {
        if (!node) return false;
        
        char ch = word[idx];
        
        if (ch < node->ch) {
            return searchHelper(node->left, word, idx);
        } else if (ch > node->ch) {
            return searchHelper(node->right, word, idx);
        } else {
            if (idx == word.length() - 1) {
                return node->isEnd;
            }
            return searchHelper(node->middle, word, idx + 1);
        }
    }
    
public:
    TernarySearchTree() : root(nullptr) {}
    
    void insert(const string& word) {
        if (!word.empty()) {
            root = insertHelper(root, word, 0);
        }
    }
    
    bool search(const string& word) {
        if (word.empty()) return false;
        return searchHelper(root, word, 0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


type Node struct {
    ch     rune
    isEnd  bool
    left   *Node
    middle *Node
    right  *Node
}

type TernarySearchTree struct {
    root *Node
}

func NewTernarySearchTree() *TernarySearchTree {
    return &TernarySearchTree{root: nil}
}

func (tst *TernarySearchTree) insertHelper(node *Node, word []rune, idx int) *Node {
    ch := word[idx]
    
    if node == nil {
        node = &Node{ch: ch, isEnd: false}
    }
    
    if ch < node.ch {
        node.left = tst.insertHelper(node.left, word, idx)
    } else if ch > node.ch {
        node.right = tst.insertHelper(node.right, word, idx)
    } else {
        if idx < len(word)-1 {
            node.middle = tst.insertHelper(node.middle, word, idx+1)
        } else {
            node.isEnd = true
        }
    }
    
    return node
}

func (tst *TernarySearchTree) searchHelper(node *Node, word []rune, idx int) bool {
    if node == nil {
        return false
    }
    
    ch := word[idx]
    
    if ch < node.ch {
        return tst.searchHelper(node.left, word, idx)
    } else if ch > node.ch {
        return tst.searchHelper(node.right, word, idx)
    } else {
        if idx == len(word)-1 {
            return node.isEnd
        }
        return tst.searchHelper(node.middle, word, idx+1)
    }
}

func (tst *TernarySearchTree) Insert(word string) {
    if len(word) > 0 {
        runes := []rune(word)
        tst.root = tst.insertHelper(tst.root, runes, 0)
    }
}

func (tst *TernarySearchTree) Search(word string) bool {
    if len(word) == 0 {
        return false
    }
    runes := []rune(word)
    return tst.searchHelper(tst.root, runes, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


class TernarySearchTree {
    private class Node {
        char ch;
        boolean isEnd;
        Node left, middle, right;
        
        Node(char c) {
            this.ch = c;
            this.isEnd = false;
        }
    }
    
    private Node root;
    
    public TernarySearchTree() {
        root = null;
    }
    
    private Node insertHelper(Node node, String word, int idx) {
        char ch = word.charAt(idx);
        
        if (node == null) {
            node = new Node(ch);
        }
        
        if (ch < node.ch) {
            node.left = insertHelper(node.left, word, idx);
        } else if (ch > node.ch) {
            node.right = insertHelper(node.right, word, idx);
        } else {
            if (idx < word.length() - 1) {
                node.middle = insertHelper(node.middle, word, idx + 1);
            } else {
                node.isEnd = true;
            }
        }
        
        return node;
    }
    
    private boolean searchHelper(Node node, String word, int idx) {
        if (node == null) return false;
        
        char ch = word.charAt(idx);
        
        if (ch < node.ch) {
            return searchHelper(node.left, word, idx);
        } else if (ch > node.ch) {
            return searchHelper(node.right, word, idx);
        } else {
            if (idx == word.length() - 1) {
                return node.isEnd;
            }
            return searchHelper(node.middle, word, idx + 1);
        }
    }
    
    public void insert(String word) {
        if (word != null && !word.isEmpty()) {
            root = insertHelper(root, word, 0);
        }
    }
    
    public boolean search(String word) {
        if (word == null || word.isEmpty()) return false;
        return searchHelper(root, word, 0);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


class Node:
    def __init__(self, ch: str):
        self.ch = ch
        self.is_end = False
        self.left = None
        self.middle = None
        self.right = None

class TernarySearchTree:
    def __init__(self):
        self.root = None
    
    def _insert_helper(self, node: Node, word: str, idx: int) -> Node:
        ch = word[idx]
        
        if node is None:
            node = Node(ch)
        
        if ch < node.ch:
            node.left = self._insert_helper(node.left, word, idx)
        elif ch > node.ch:
            node.right = self._insert_helper(node.right, word, idx)
        else:
            if idx < len(word) - 1:
                node.middle = self._insert_helper(node.middle, word, idx + 1)
            else:
                node.is_end = True
        
        return node
    
    def _search_helper(self, node: Node, word: str, idx: int) -> bool:
        if node is None:
            return False
        
        ch = word[idx]
        
        if ch < node.ch:
            return self._search_helper(node.left, word, idx)
        elif ch > node.ch:
            return self._search_helper(node.right, word, idx)
        else:
            if idx == len(word) - 1:
                return node.is_end
            return self._search_helper(node.middle, word, idx + 1)
    
    def insert(self, word: str) -> None:
        if word:
            self.root = self._insert_helper(self.root, word, 0)
    
    def search(self, word: str) -> bool:
        if not word:
            return False
        return self._search_helper(self.root, word, 0)

Complexity

⏰ Time complexity: O(log n + m) average case for search and insert, where n is number of nodes and m is word length. Worst case O(n + m) for skewed tree
🧺 Space complexity: O(n) for storing n nodes, plus O(m) recursion stack depth during operations

Method 2 - Iterative Implementation with Explicit Stack

Intuition

Instead of using recursion, we can implement the ternary search tree operations iteratively using explicit stacks or direct pointer manipulation. This approach can be more memory efficient and avoids potential stack overflow issues for very deep trees.

Approach

Use iterative traversal for both insertion and search operations
Maintain current node pointer and traverse based on character comparison
For insertion, create nodes as needed and handle parent-child linking explicitly
For search, follow the same logic but without node creation
Track parent nodes to enable proper linking during insertion

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


class TernarySearchTreeIterative {
private:
    struct Node {
        char ch;
        bool isEnd;
        Node* left;
        Node* middle;
        Node* right;
        
        Node(char c) : ch(c), isEnd(false), left(nullptr), middle(nullptr), right(nullptr) {}
    };
    
    Node* root;
    
public:
    TernarySearchTreeIterative() : root(nullptr) {}
    
    void insert(const string& word) {
        if (word.empty()) return;
        
        Node** curr = &root;
        int idx = 0;
        
        while (idx < word.length()) {
            char ch = word[idx];
            
            if (*curr == nullptr) {
                *curr = new Node(ch);
            }
            
            if (ch < (*curr)->ch) {
                curr = &((*curr)->left);
            } else if (ch > (*curr)->ch) {
                curr = &((*curr)->right);
            } else {
                if (idx == word.length() - 1) {
                    (*curr)->isEnd = true;
                    break;
                }
                curr = &((*curr)->middle);
                idx++;
            }
        }
    }
    
    bool search(const string& word) {
        if (word.empty()) return false;
        
        Node* curr = root;
        int idx = 0;
        
        while (curr && idx < word.length()) {
            char ch = word[idx];
            
            if (ch < curr->ch) {
                curr = curr->left;
            } else if (ch > curr->ch) {
                curr = curr->right;
            } else {
                if (idx == word.length() - 1) {
                    return curr->isEnd;
                }
                curr = curr->middle;
                idx++;
            }
        }
        
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


type TernarySearchTreeIterative struct {
    root *Node
}

func NewTernarySearchTreeIterative() *TernarySearchTreeIterative {
    return &TernarySearchTreeIterative{root: nil}
}

func (tst *TernarySearchTreeIterative) Insert(word string) {
    if len(word) == 0 {
        return
    }
    
    runes := []rune(word)
    curr := &tst.root
    idx := 0
    
    for idx < len(runes) {
        ch := runes[idx]
        
        if *curr == nil {
            *curr = &Node{ch: ch, isEnd: false}
        }
        
        if ch < (*curr).ch {
            curr = &((*curr).left)
        } else if ch > (*curr).ch {
            curr = &((*curr).right)
        } else {
            if idx == len(runes)-1 {
                (*curr).isEnd = true
                break
            }
            curr = &((*curr).middle)
            idx++
        }
    }
}

func (tst *TernarySearchTreeIterative) Search(word string) bool {
    if len(word) == 0 {
        return false
    }
    
    runes := []rune(word)
    curr := tst.root
    idx := 0
    
    for curr != nil && idx < len(runes) {
        ch := runes[idx]
        
        if ch < curr.ch {
            curr = curr.left
        } else if ch > curr.ch {
            curr = curr.right
        } else {
            if idx == len(runes)-1 {
                return curr.isEnd
            }
            curr = curr.middle
            idx++
        }
    }
    
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


class TernarySearchTreeIterative {
    private class Node {
        char ch;
        boolean isEnd;
        Node left, middle, right;
        
        Node(char c) {
            this.ch = c;
            this.isEnd = false;
        }
    }
    
    private Node root;
    
    public TernarySearchTreeIterative() {
        root = null;
    }
    
    public void insert(String word) {
        if (word == null || word.isEmpty()) return;
        
        Node curr = root;
        Node parent = null;
        int direction = 0; // 0: root, 1: left, 2: middle, 3: right
        int idx = 0;
        
        while (idx < word.length()) {
            char ch = word.charAt(idx);
            
            if (curr == null) {
                curr = new Node(ch);
                if (parent == null) {
                    root = curr;
                } else {
                    switch (direction) {
                        case 1: parent.left = curr; break;
                        case 2: parent.middle = curr; break;
                        case 3: parent.right = curr; break;
                    }
                }
            }
            
            if (ch < curr.ch) {
                parent = curr;
                curr = curr.left;
                direction = 1;
            } else if (ch > curr.ch) {
                parent = curr;
                curr = curr.right;
                direction = 3;
            } else {
                if (idx == word.length() - 1) {
                    curr.isEnd = true;
                    break;
                }
                parent = curr;
                curr = curr.middle;
                direction = 2;
                idx++;
            }
        }
    }
    
    public boolean search(String word) {
        if (word == null || word.isEmpty()) return false;
        
        Node curr = root;
        int idx = 0;
        
        while (curr != null && idx < word.length()) {
            char ch = word.charAt(idx);
            
            if (ch < curr.ch) {
                curr = curr.left;
            } else if (ch > curr.ch) {
                curr = curr.right;
            } else {
                if (idx == word.length() - 1) {
                    return curr.isEnd;
                }
                curr = curr.middle;
                idx++;
            }
        }
        
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


class TernarySearchTreeIterative:
    def __init__(self):
        self.root = None
    
    def insert(self, word: str) -> None:
        if not word:
            return
        
        curr = self.root
        parent = None
        direction = 0  # 0: root, 1: left, 2: middle, 3: right
        idx = 0
        
        while idx < len(word):
            ch = word[idx]
            
            if curr is None:
                curr = Node(ch)
                if parent is None:
                    self.root = curr
                else:
                    if direction == 1:
                        parent.left = curr
                    elif direction == 2:
                        parent.middle = curr
                    elif direction == 3:
                        parent.right = curr
            
            if ch < curr.ch:
                parent = curr
                curr = curr.left
                direction = 1
            elif ch > curr.ch:
                parent = curr
                curr = curr.right
                direction = 3
            else:
                if idx == len(word) - 1:
                    curr.is_end = True
                    break
                parent = curr
                curr = curr.middle
                direction = 2
                idx += 1
    
    def search(self, word: str) -> bool:
        if not word:
            return False
        
        curr = self.root
        idx = 0
        
        while curr is not None and idx < len(word):
            ch = word[idx]
            
            if ch < curr.ch:
                curr = curr.left
            elif ch > curr.ch:
                curr = curr.right
            else:
                if idx == len(word) - 1:
                    return curr.is_end
                curr = curr.middle
                idx += 1
        
        return False

Complexity

⏰ Time complexity: O(log n + m) average case, O(n + m) worst case, same as recursive version but with constant stack space
🧺 Space complexity: O(n) for storing nodes, O(1) additional space for operations (no recursion stack)

Notes

Method 1 provides a clean recursive implementation that’s easier to understand and implement
Method 2 offers an iterative approach that avoids recursion stack overhead and potential stack overflow
Ternary search trees combine benefits of tries (prefix-based operations) and binary search trees (balanced structure)
The tree structure naturally maintains lexicographic order, making operations like finding all words with a prefix efficient
Space efficiency is better than standard tries as each node stores only one character
The tree can become unbalanced with certain insertion orders, leading to degraded performance
Self-balancing variants exist but add implementation complexity
Useful for applications like auto-completion, spell checkers, and symbol tables in compilers
The middle child represents character continuation while left/right children provide lexicographic ordering
Each word must be explicitly marked as complete using the isEnd flag to distinguish between prefixes and actual words

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Standard Ternary Search Tree Implementation#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Iterative Implementation with Explicit Stack#

Intuition#

Approach#

Code#

Complexity#

Notes#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Standard Ternary Search Tree Implementation

Intuition

Approach

Code

Complexity

Method 2 - Iterative Implementation with Explicit Stack

Intuition

Approach

Code

Complexity

Notes