Data Structures Using C, 2nd Edition by Pearson

Trees 345

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 ...