Since a binary search tree with N nodes has N + 1 null references, half the space allocated in a binary search tree for link information is wasted.

Consider that if a node has a null left child, we make its left child link to its inorder predecessor, and if a node has a null right child, we make its right child link to its inorder successor.

This is known as a threaded tree, and the extra links are called threads.

Question -1 How can we distinguish threads from real children links?

Question -2 Design the routines to perform insertion and deletion into a tree threaded in the manner described above.

Question -3 What is the advantage of using threaded trees?

Please show all your work and give an explanation of steps