It may be noted that the node containing ‘T’ has become the left child of node containing ‘F’. After the
insertion, the tree is still a threaded binary tree. The predecessor of ‘T’ is ‘A’ and the successor of ‘T’ is ‘F’.
An algorithm for insertion of node as left thread is given below:
Algorithm insertAtLThread(X,Y)
{
if (LTag(Y) == 0)
{
LTag (X) =0;
leftChild (X) = leftChild (Y);
LTAg (Y) =1;
leftChild (Y) = X;
RTag (X) = 0;
rightChild (X) = Y;
}
}
CASE 2:
When Y (Data part equal to ‘F’) has an empty right child, then it must be a thread. The insertion can be made
by making the right thread of X (Data part equal to ‘T ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.