Ternary search tree is a type of trie (sometimes called a prefix tree), unlike trie(standard) data structure where each node contains max 26 pointers for its children, each node in a ternary search tree contains only 3 pointers.

Pointers in Ternary Tree:

  1. The left pointer points to the node whose value is less than the value of the current node.
  2. The equal pointer points to the node whose value is equal to/close to the value of the current node.
  3. The right pointer points to the node whose value is greater than the value of the current node.

 

ref:http://d1hyf4ir1gqw6c.cloudfront.net//wp-content/uploads/Ternary-Search-Tree.png 

Complexity:

  • Time Complexity
  • Space Complexity
    • Ternary search trees are more space efficient compared to standard prefix trees.