Tutorial 5: Binary Search Tree

CAB301 - Algorithms and Complexity

School of Computer Science, Faculty of Science

Agenda

  1. Lecture Recap: Binary Tree and Binary Search Tree
    • Binary Tree Traversal
    • Binary Search Tree Operations:
      • Search
      • Insertion
      • Deletion
  2. Tutorial Questions + Q&A
CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Binary Tree

Each node has at most two children: left and right.

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Binary Search Tree

In a Binary Search Tree (BST), for each node:

  • All nodes in the left subtree have smaller values.
  • All nodes in the right subtree have greater values.

Any operation must maintain the BST property.

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Binary Tree Traversal

In-order: Left, Root, Right

Pre-order: Root, Left, Right

Post-order: Left, Right, Root

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Search Operation

Search is similar to Binary Search:

ALGORITHM Search(, )
if
if
return
else if
return Search(, )
else
return Search(, )
else
return

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Insertion Operation

Insertion is similar to Search:

ALGORITHM Insert(, )
if
new Node; ;
else
if
if
new Node


else
else
if
new Node


else

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science

Deletion Operation

Deletion is more complex:

  • Case 1: Node has no children (leaf node). Simply remove it.
  • Case 2: Node has one child (left or right). Replace it with the child.
  • Case 3: Node has two children (left and right)

CAB301 - Algorithms and Complexity
School of Computer Science, Faculty of Science