Binary Tree Operations, Sorting Algorithms & CLL Pseudocode

Posted on Jan 30, 2026 in Computer Engineering in Computer Engineering

Binary Tree Insert

1. ptr = ROOT; flag = FALSE
2. While (ptr != NULL) and (flag == FALSE) do
3.   Case: ITEM < ptr->DATA
4.     ptr1 = ptr
5.     ptr = ptr->LCHILD
6.   Case: ITEM > ptr->DATA
7.     ptr1 = ptr
8.     ptr = ptr->RCHILD
9.   Case: ptr->DATA = ITEM
10.    flag = TRUE
11.    Print "ITEM already exists"
12.    Exit
13.  EndCase
14. EndWhile
15. If (ptr == NULL) then
16.   new = GetNode(NODE)
17.   new->DATA = ITEM
18.   new->LCHILD = NULL
19.   new->RCHILD = NULL
20.   If (ptr1->DATA < ITEM) then
21.     ptr1->RCHILD = new
22.   Else
23.     ptr1->LCHILD = new
24.   EndIf
25. EndIf
26. Stop

Binary Tree Delete

ptr = ROOT; flag = FALSE
2. While (ptr != NULL) and (flag == FALSE) do
3.   Case: ITEM < ptr->DATA
4.     parent = ptr
5.     ptr = ptr->LCHILD
6.   Case: ITEM > ptr->DATA
7.     parent = ptr
8.     ptr = ptr->RCHILD
9.   Case: ptr->DATA = ITEM
10.    flag = TRUE
11.  EndCase
12. EndWhile
13. If (flag == FALSE) then
14.    Print "ITEM does not exist: No deletion"
15.    Exit
16. EndIf
17. If (ptr->LCHILD == NULL) and (ptr->RCHILD == NULL) then
18.    case = 1
19. Else
20.    If (ptr->LCHILD != NULL) and (ptr->RCHILD != NULL) then
21.      case = 3
22.    Else
23.      case = 2
24.    EndIf
25. EndIf

Selection Sort (SelectionSort(A, n))

1. Algorithm: SelectionSort(A, n)
2. For i = 0 to n - 1 do
2.1 min_idx = i
3. For j = i + 1 to n do
3.1 If (A[j] < A[min_idx]) then
3.1.1 min_idx = j
     EndIf
   j = j + 1
 EndFor
4. If (min_idx != i) then
4.1 swap(A[min_idx], A[i])
 EndIf
 i = i + 1
 EndFor
Stop

Insertion Sort (InsertionSort(A, n))

Algorithm: InsertionSort(A, n)
1. i = 1
2. While i < n do
     key = A[i]
     j = i - 1
     While (j >= 0 and A[j] > key) do
         A[j + 1] = A[j]
         j = j - 1
     EndWhile
     A[j + 1] = key
     i = i + 1
 EndWhile
End

Merge Sort (MergeSort(A, low, high))

Algorithm: MergeSort(A, low, high)
Begin
 If (low < high) then
     mid = (low + high) / 2
     MergeSort(A, low, mid)
     MergeSort(A, mid + 1, high)
     Merge(A, low, mid, high)
 EndIf
End

Merge (Merge(A, low, mid, high))

Algorithm: Merge(A, low, mid, high)
Set i = low, j = mid + 1, k = 0
While (i <= mid and j <= high) do
    If (A[i] <= A[j]) then
        B[k] = A[i]
        i = i + 1
    Else
        B[k] = A[j]
        j = j + 1
    EndIf
    k = k + 1
EndWhile
While (i <= mid) do
    B[k] = A[i]
    i = i + 1; k = k + 1
EndWhile
While (j <= high) do
    B[k] = A[j]
    j = j + 1; k = k + 1
EndWhile
Copy array B to array A from low to high

Circular Linked List (CLL)

CLL

Traverse()
 temp = head
 while (temp->link != head)
     print temp->data
     temp = temp->link
 print temp->data

Insert_Front()
 newnode = malloc(sizeof(struct node))
 if (head == NULL)
     head = tail = newnode
     newnode->link = head
 else
     newnode->link = head
     head = newnode
     tail->link = head

Insert_End()
 repeat
     tail->link = newnode
     tail = newnode
     tail->link = head

Insert_After_Key()
 repeat
 read key
 temp = head
 while (temp->data != key)
     temp = temp->link
     if (temp == head) return
 newnode->link = temp->link
 temp->link = newnode
 if (temp == tail) tail = newnode

Insert_At_Position()
 newnode
 if (head == NULL && pos != 0) return
 read pos, value
 newnode->data = value
 temp = head
 for i = 1 to pos - 1
     temp = temp->link
 newnode->link = temp->link
 temp->link = newnode
 if (pos == 0)
     newnode->link = head
     head = newnode
     tail->link = head
 if (temp == tail) tail = newnode

Delete Operations for CLL

Delete_Front()
 if (head == NULL) return
 if (head->link == head)
     free(head)
     head = NULL
 else
     temp = head
     head = head->link
     tail->link = head
     free(temp)

Delete_End()
 repeat
     head = tail = NULL
 else
     temp = head
     while (temp->link != tail)
         temp = temp->link
     free(tail)
     tail = temp
     tail->link = head

Delete_Key()
 read key
 if (head == NULL) return
 temp = head
 while (temp->data != key && temp->link != head)
     prev = temp
     temp = temp->link
 if (temp->data != key) return
 if (temp == head)
     head = head->link
     tail->link = head
 else
     prev->link = temp->link
     if (temp == tail) tail = prev
 free(temp)

Delete_At_Position()
 if (head == NULL) return
 read pos
 if (pos == 1)
     if (head->link == head)
         head = tail = NULL
     else
         head = head->link
         tail->link = head
     return
 temp = head
 for i = 1 to pos - 1
     prev = temp
     temp = temp->link
 prev->link = temp->link
 if (temp == tail) tail = prev
 free(temp)

Inorder Traversal (Iterative)

Begin
    temp = root
    while (top > -1) or (temp != NULL) do
        if (temp != NULL) then
            push(temp)
            temp = temp->left
        else
            temp = pop()
            print(temp->data)
            temp = temp->right
        endif
    endwhile
 End

Preorder Traversal (Iterative)

Begin
    temp = root
    while (top > -1) or (temp != NULL) do
        if (temp != NULL) then
            print(temp->data)
            push(temp)
            temp = temp->left
        else
            temp = pop()
            temp = temp->right
        endif
    endwhile
 End

Postorder Traversal (Two Stacks)

Begin
    temp = root
    if (root == NULL) then
        return
    endif
    create two stacks s1 and s2
    push(s1, temp)
    while (s1 is not empty) do
        node = pop(s1)
        push(s2, node)
        if (node->left != NULL) then
            push(s1, node->left)
        endif
        if (node->right != NULL) then
            push(s1, node->right)
        endif
    endwhile
    while (s2 is not empty) do
        node = pop(s2)
        print(node->data)
    endwhile
 End

Duplicate: Selection Sort (Repeated)

Algorithm: SelectionSort(A, n)
2. For i = 0 to n - 1 do
2.1.min_idx = i
3,For j = i + 1 to n do
3.1,If (A[j] < A[min_idx]) then
3.1.1 min_idx = j EndIf
j = j + 1 EndFor 4, If (min_idx != i) then
4.1swap(A[min_idx], A[i])
EndIf i = i + 1 EndFor Stop

Duplicate: Insertion Sort (Repeated)

Algorithm: InsertionSort(A, n)
i = 1  While i < n do
        key = A[i]
        j = i - 1
        While (j >= 0 and A[j] > key) do
            A[j + 1] = A[j]
            j = j - 1
        EndWhile
        A[j + 1] = key
        i = i + 1
    EndWhile End

Duplicate: Merge Sort and Merge (Repeated)

Algorithm: MergeSort(A, low, high)
Begin If (low < high) then
        mid = (low + high) / 2
        MergeSort(A, low, mid)
        MergeSort(A, mid + 1, high)
        Merge(A, low, mid, high)
    EndIf End

Algorithm: Merge(A, low, mid, high)
Set i = low, j = mid + 1, k = 0
    While (i <= mid and j <= high) do
        If (A[i] <= A[j]) then
            B[k] = A[i]
            i = i + 1 Else
            B[k] = A[j]
            j = j + 1 EndIf
        k = k + 1 EndWhile
    While (i <= mid) do
        B[k] = A[i]
        i = i + 1, k = k + 1 EndWhile
    While (j <= high) do
        B[k] = A[j]
        j = j + 1, k = k + 1 EndWhile
    Copy array B to array A from low to high

Duplicate: Circular Linked List (Repeated)

CLL
Traverse()
temp = head
while(temp->link != head)
    print temp->data
    temp = temp->link
print temp->data
Insert_Front()
newnode = malloc(sizeof(struct node))
if(head == NULL)
    head = tail = newnode
    newnode->link = headelse 
newnode->link = head head = newnode
tail->link = head
Insert_End()
repeat
    tail->link = newnode
    tail = newnode
    tail->link = head
Insert_After_Key()
repeat
read key
temp = head
while(temp->data != key)
    temp = temp->link
    if(temp == head) return
newnode->link = temp->link
temp->link = newnode
if(temp == tail) tail = newnode
Insert_At_Position()
newnode
if(head == NULL && pos != 0) return
read pos, value
newnode->data = value
temp = head
for i = 1 to pos - 1
    temp = temp->link
newnode->link = temp->link
temp->link = newnode
if(pos == 0)
    newnode->link = head
    head = newnode
    tail->link = head
if(temp == tail) tail = newnode
Delete_Front()
if(head == NULL) return
if(head->link == head)
    free(head)
    head = NULL
else
    temp = head
    head = head->link
    tail->link = head
    free(temp)
Delete_End()
repeat
    head = tail = NULL
else
    temp = head
    while(temp->link != tail)
        temp = temp->link
    free(tail)
    tail = temp
    tail->link = head
Delete_Key()
read key
if(head == NULL) return
temp = head
while(temp->data != key && temp->link != head)
    prev = temp
    temp = temp->link
if(temp->data != key) return
if(temp == head)
    head = head->link
    tail->link = head
else
    prev->link = temp->link
    if(temp == tail) tail = prev
free(temp)

Delete_At_Position()
if(head == NULL) return
read pos
if(pos == 1)
    if(head->link == head)
        head = tail = NULL
    else
        head = head->link
        tail->link = head
    return
temp = head
for i = 1 to pos - 1
    prev = temp
    temp = temp->link
prev->link = temp->link
if(temp == tail) tail = prev
free(temp)

Duplicate: Traversals (Repeated)

Inorder Traversal
Begin
    temp = root
    while (top > -1) or (temp != NULL) do
        if (temp != NULL) then
            push(temp)
            temp = temp->left
        else
            temp = pop()
            print(temp->data)
            temp = temp->right
        endif
    endwhile
 End

Preorder Traversal
Begin
    temp = root
    while (top > -1) or (temp != NULL) do
        if (temp != NULL) then
            print(temp->data)
            push(temp)
            temp = temp->left
        else
            temp = pop()
            temp = temp->right
        endif
    endwhile
 End

Postorder Traversal
Begin
    temp = root
    if (root == NULL) then
        return
    endif
    create two stacks s1 and s2
    push(s1, temp)
    while (s1 is not empty) do
        node = pop(s1)
        push(s2, node)
        if (node->left != NULL) then
            push(s1, node->left)
        endif
        if (node->right != NULL) then
            push(s1, node->right)
        endif
    endwhile
    while (s2 is not empty) do
        node = pop(s2)
        print(node->data)
    endwhile
 End