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.