Answer the following questions about the Ternary Search Tree

Answer the following questions about the Ternary Search Tree (TST) data structure. The TST is a linked data structure similar to a BST, but with a few differences. Each node of the TST has 6 fields:

- hasTwo: Boolean indicating whether this node contains two elements (true) or just one (false)

- lo: data element (integer) that this node contains

- hi: another integer that this node contains; must be greater than or equal to lo; may be uninitialized if hasTwo is false

- left: pointer to another TST node; all nodes of the left subtree must contain values less than or equal to lo

- right: pointer to another TST node; all nodes of the right subtree must
contain values greater than or equal to hi

- mid: pointer to another TST node; all nodes of the middle subtree must contain values between lo and hi

Additionally, all TST nodes will have at least one data element (lo), and no TST node can have children (all 3 pointers NIL) until it contains two data elements (lo and hi).

1. Give pseudocode for a Insert method for the TSTNode class (i.e., TSTNode.Insert) that accepts an integer x and adds it to a node in the subtree rooted at this node so that all TST properties are maintained. This method should not return anything. You may assume that TSTNode has a valid one-element constructor, TSTNode(x).

2. How does the worst-case complexity of this method compare to inserting an element into a BST with n elements? Justify your answer.

Solution

Question 1:-

// A node of ternary search tree
struct Node
{
    //data element (integer) that this node contains
    int lo;
  
    //another integer that this node contains greater than or equal to lo
    int hi;

    // True if both hi and lo values are present in the current node
    bool hasTwo;
  
    //Three pointers to leftSubtree, rightSubtree, midSubtree
    struct Node *left, *mid, *right;
};

// A utility function to create a new ternary search tree node like a constructor in java
struct Node* newNode(int x)
{
    //Allocate memory for newNode
    struct Node* temp = (struct Node*) malloc(sizeof( struct Node ));
    temp->lo = x;
    temp->hasTwo = false;
    temp->left = temp->mid = temp->right = NULL;
    return temp;
}

// Function to insert a new word in a Ternary Search Tree
void insert(struct Node** root, int data)
{
    // Base Case: Tree is empty
    if (!(*root))
        *root = newNode(data);
  
    // If the root has only single element we have to insert the second element as lo or hi
    if((*root)->hasTwo == false){
        if(data > (*root)->lo){
            (*root)->hi = data;
            hasTwo = true;
        }else{
            (*root)->hi = (*root)->lo;
            (*root)->lo = data;
            hasTwo = true;
        }
    }
    //If the root has both the elements , then put the data in a sub tree rooted at left, mid or right
    else{
        if(data <= (*root)->left){
            insert(&((*root)->left),data); //insert in left sub tree
        }
        else if(data <=((*root)->right)){
            insert(&((*root)->mid),data); //insert in mid sub tree
        }
        else{
            insert(&((*root)->right),data); //insert in right sub tree
        }
      
    }
}

Question 2:-

The time complexity of the ternary search tree operations is similar to that of binary search tree(BST).
The insertion, deletion and search operations take time proportional to the height of the ternary search tree.
The space Complexity is proportional to the length of the total data to be stored.

Worst Case Time Complexity in BST:- O(n)
This case occurs when the sorted order of elements are getting inserted.
Example:- 1,2,3,4,5,6,7
Then the elements are to be inserted in the BST in left subtree each time an insert operation occurs. So the time complexity is O(n) where n is the number of elements inserted.

Worst Case Time Complexity in Ternary Search Tree:- O(n)
This is also the same case as above.
But instead of putting each element in the left sub tree or right sub tree, here a child is created only after lo and hi both are full in the current node.
Any way a traverse operation takes O(1) time. So total time complexity of inserting in a Ternary search tree os O(n) in the worst case.