Data Structure Algorithms: BST, Sort, and CLL Operations

Posted on Dec 13, 2025 in Computer Engineering in Computer Engineering

Binary Tree Insertion

  1. ptr = ROOT, flag = FALSE
  2. While (ptr != NULL) and (flag = FALSE) do:
  • Case: ITEM < ptr→DATA
  1. ptr1 = ptr
  2. ptr = ptr→LCHILD
Case: ITEM > ptr→DATA
  1. ptr1 = ptr
  2. ptr = ptr→RCHILD
Case: ptr→DATA = ITEM
  1. flag = TRUE
  2. Print “ITEM already exists”
  3. Exit
EndWhile If (ptr = NULL) then:
  • new = GetNode(NODE)
  • new→DATA = ITEM
  • new→LCHILD = NULL
  • new→RCHILD = NULL
  • If (ptr1→DATA < ITEM) then
    • ptr1→RCHILD = new
  • Else
    • ptr1→LCHILD = new
  • EndIf
EndIf Stop

Binary Tree Deletion

  1. ptr = ROOT, flag = FALSE
  2. While (ptr != NULL) and (flag = FALSE) do:
  • Case: ITEM < ptr→DATA
  1. parent = ptr
  2. ptr = ptr→LCHILD
Case: ITEM > ptr→DATA
  1. parent = ptr
  2. ptr = ptr→RCHILD
Case: ptr→DATA = ITEM
  1. flag = TRUE
EndCase EndWhile If (flag = FALSE) then:
  • Print “ITEM does not exist: No deletion”
  • Exit
EndIf If (ptr→LCHILD = NULL) and (ptr→RCHILD = NULL) then:
  • case = 1
Else
  • If (ptr→LCHILD != NULL) and (ptr→RCHILD != NULL) then:
    • case = 3
  • Else
    • case = 2
  • EndIf
EndIf

Algorithm: SelectionSort(A, n)

  1. For i = 0 to n – 1 do:
  • min_idx = i
  • For j = i + 1 to n do:
    • If (A[j] < A[min_idx]) then:
      • min_idx = j
    • EndIf
    • j = j + 1
  • EndFor
  • If (min_idx != i) then:
    • swap(A[min_idx], A[i])
  • EndIf
  • i = i + 1
EndFor Stop

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

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)

  1. Set i = low, j = mid + 1, k = 0
  2. 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) Operations

Traverse()

  1. temp = head
  2. while(temp->link != head):
  • print temp->data
  • temp = temp->link
print temp->data

Insert_Front()

  1. newnode = malloc(sizeof(struct node))
  2. if(head == NULL):
  • head = tail = newnode
  • newnode->link = head
else:
  • newnode->link = head
  • head = newnode
  • tail->link = head

Insert_End()

  1. repeat:
  • tail->link = newnode
  • tail = newnode
  • tail->link = head

Insert_After_Key()

  1. 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()

  1. newnode
  2. if(head == NULL && pos != 0) return
  3. read pos, value
  4. newnode->data = value
  5. temp = head
  6. 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()

  1. if(head == NULL) return
  2. if(head->link == head):
  • free(head)
  • head = NULL
else:
  • temp = head
  • head = head->link
  • tail->link = head
  • free(temp)

Delete_End()

  1. repeat:
  • head = tail = NULL
else:
  • temp = head
  • while(temp->link != tail):
    • temp = temp->link
  • free(tail)
  • tail = temp
  • tail->link = head

Delete_Key()

  1. read key
  2. if(head == NULL) return
  3. temp = head
  4. 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()

  1. if(head == NULL) return
  2. read pos
  3. 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)

Binary Tree Traversal

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