Deal with fully-threaded BSTs, in which not only are null right links replaced with threads to in order successors, as described in the text, but also null left links are replaced with threads to in order predecessors.
Write an algorithm to insert a node into a fully threaded BST so that the resulting BST is also fully threaded.