Problem
I. Show that in a binary tree of N nodes, there are N + 1 null links representing children.
II. A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
III. 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. Suppose 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.
i. How can we distinguish threads from real children links?
ii. Write routines to perform insertion and deletion into a tree threaded in the manner described above.
iii. What is the advantage of using threaded trees?