Page 236 - DCAP407_DATA_STRUCTURE

Unit 12: Binary Tree Traversals and Operations

Steps
1. L = SEARCH_SEQ(1, KEY) // Search for key node in the tree
2. If (L = 0) then
(a) Print “Search is unsuccessful: No insertion”

(b) Exit
3. EndIf // Quit execution
4. If (A[2 * L] = NULL) or (a[2 * L +1] = NULL)then //If the left and right sub-trees are
empty
(a) Read option to read as left (L) or right (R) //child (give option = L/R)

(b) If (option = L) then
(i) If A[2 * L] = NULL then //Left link is empty
1. A[2 * L] = ITEM // Store it in the array A
(ii) Else // Cannot be inserted as left child
1. Print “Desired insertion is not possible” //already has left child
2. Exit //Return to end of procedure
(iii) EndIf

(c) EndIf
(d) If (option = R) then //Move to right side
(i) If (A[2 * L +1] = NULL) then // Right link is empty
1. A[2 * L +1] = ITEM //Store it in the array A
(ii) Else //Cannot be inserted as right child
1. Print “Desired operation is not possible” //already has a right child
2. Exit // Return to the end of procedures

(iii) EndIf
(e) EndIf //Key node having both the child
5. Else //Key node does not have any empty link
(a) Print “ITEM cannot be inserted as leaf node”
6. EndIf
7. Stop
The recursive algorithm of search operation for inserting a node is as follows:

Input – KEY is the item of search, INDEX is the index of node from which the searching process starts.
Output – LOCATION is where the item KEY is located
Data structure – Array A is for storing binary tree. SIZE indicates the size of A
Steps
1. L = SEARCH_SEQ(1, KEY)
i = INDEX //Start search from the root node

2. If (A[i] ≠ KEY) then //Present node is not key node
1. If (2 * i ≤ SIZE) then //If left sub-tree is not exhausted

LOVELY PROFESSIONAL UNIVERSITY 229