Question

Since a binary search tree with N nodes has N + 1 NULL pointers, half the space allocated in a binary search tree for pointer information is wasted. Suppose that if a node has a NULL left child, we make its left child point to its inorder predecessor, and if a node has a NULL right child, we make its right child point to its inorder successor. This is known as a threaded tree and the extra pointers are called threads.

a. How can we distinguish threads from real children pointers?
b. Write routines to perform insertion and deletion into a tree threaded in the manner described above.
c. What is the advantage of using threaded trees? 4.46 A

Answer 1

Threads in a threaded binary search tree can be distinguished from real children pointers using a unique marker or special value. Insertion and deletion in a threaded tree involve updating child pointers or threads to maintain the proper binary search tree structure. The advantage of using threaded trees is faster and more efficient traversal without the need for recursive calls or a stack.

Step-by-step explanation:

a. Threads in a threaded binary search tree can be distinguished from real children pointers by using a special value, such as NULL or a unique marker, to represent a thread. This allows us to differentiate between actual child pointers and threads when traversing the tree.b. To perform insertion into a threaded tree, we first need to find the correct position for the new node using the binary search tree property. Once we find the position, we update the appropriate child pointer or thread to point to the new node. To perform deletion, we first locate the node to be deleted. If the node has a thread, we update the appropriate child pointer or thread of its parent to skip the node.

If the node has actual children, we replace it with its inorder predecessor or inorder successor and update the appropriate child pointers and threads.c. The advantage of using threaded trees is that they allow for faster and more efficient traversal operations. In a regular binary search tree, inorder traversal requires recursive calls or a stack to keep track of the nodes. However, in a threaded tree, we can traverse the tree without additional function calls or stack usage, as the threads provide direct links to the inorder predecessor and successor of each node.