Unit 8 – Trees, Binary Trees, BST Operations, Traversals & Heap

1. What is a Tree?

A tree is a connected, acyclic graph with a distinguished node called the root.
Key terms

Visualising a generic tree

Figure 1 – Simple rooted tree

2. Binary Trees

A binary tree restricts each node to at most two children, conventionally called left and right.

2.1 Common binary‑tree categories

2.2 Representations

2.2.1 Linked‑node representation

Figure 2 – Linked‑node binary tree (root 30)

2.2.2 Array (implicit) representation

Parent of index i = ⌊i/2⌋, left child = 2i, right child = 2i+1.

3. Binary Search Tree (BST)

A BST satisfies:

• key(left subtree) < key(node) < key(right subtree) for every node.

This ordering yields average‑case O(log n) search, insert and delete.

3.1 Insertion

Algorithm (mermaid flowchart)

flowchart TD
    A["Start: newKey"] --> B["curr = root"]
    B --> C{"curr == NULL?"}
    C -- Yes --> D["Insert new node here"]
    C -- No --> E{"newKey < curr.key?"}
    E -- Yes --> F["curr = curr.left"]
    E -- No --> G["curr = curr.right"]
    F --> C
    G --> C
    D --> H["End"]
    H --> I["Return"]

C implementation

typedef struct Node {
    int key;
    struct Node *left, *right;
} Node;

Node* newNode(int k) {
    Node* n = malloc(sizeof(Node));
    n->key = k; n->left = n->right = NULL;
    return n;
}

Node* insertBST(Node* root, int k) {
    if (root == NULL) return newNode(k);
    if (k < root->key)
        root->left = insertBST(root->left, k);
    else if (k > root->key)
        root->right = insertBST(root->right, k);
    return root;
}

Worked example

Insert the keys 30, 20, 40, 10, 25 in that order.

Figures 3‑7 (generated automatically) show the tree after each insertion.

3.2 Deletion

Three cases:

1. Leaf node – simply remove.
2. Node with one child – replace node with its child.
3. Node with two children – replace with in‑order successor (minimum in right subtree) and delete that successor.

Algorithm (mermaid)

flowchart TD
    A["Start: deleteKey"] --> B["curr = root, parent = NULL"]
    B --> C{"curr == NULL?"}
    C -- Yes --> D["Key not found → End"]
    C -- No --> E{"key < curr.key?"}
    E -- Yes --> F["parent = curr; curr = curr.left"]
    E -- No --> G{"key > curr.key?"}
    G -- Yes --> H["parent = curr; curr = curr.right"]
    G -- No --> I["Node found"]
    F --> C
    H --> C
    I --> J{"curr has 0/1/2 children?"}
    J -->|"0"| K["Remove leaf"]
    J -->|"1"| L["Replace with its child"]
    J -->|"2"| M["Find inorder successor S"]
    M --> N["Copy S.key to curr"]
    N --> O["Delete S (leaf or one‑child)"]
    K --> P["End"]
    L --> P
    O --> P

C implementation (simplified)

Node* minValueNode(Node* node) {
    while (node->left) node = node->left;
    return node;
}

Node* deleteBST(Node* root, int k) {
    if (!root) return NULL;
    if (k < root->key) root->left = deleteBST(root->left, k);
    else if (k > root->key) root->right = deleteBST(root->right, k);
    else {
        if (!root->left) { Node* tmp = root->right; free(root); return tmp; }
        if (!root->right) { Node* tmp = root->left; free(root); return tmp; }
        Node* succ = minValueNode(root->right);
        root->key = succ->key;
        root->right = deleteBST(root->right, succ->key);
    }
    return root;
}

Example: delete 20 from the tree built earlier

4. Tree Traversals

4.1 Recursive implementations (C)

void inorder(Node* r){ if(r){ inorder(r->left); printf("%d ",r->key); inorder(r->right);} }
void preorder(Node* r){ if(r){ printf("%d ",r->key); preorder(r->left); preorder(r->right);} }
void postorder(Node* r){ if(r){ postorder(r->left); postorder(r->right); printf("%d ",r->key);} }

4.2 Level‑order (iterative) using a queue

void levelOrder(Node* root){
    if(!root) return;
    Queue q; initQueue(&q);
    enqueue(&q, root);
    while(!isEmpty(&q)){
        Node* cur = dequeue(&q);
        printf("%d ", cur->key);
        if(cur->left)  enqueue(&q, cur->left);
        if(cur->right) enqueue(&q, cur->right);
    }
}

Trace of inorder on the final tree (30,25,40,10)

5. Binary Heap & Heap‑Sort

A binary heap is a complete binary tree that satisfies the heap property:

• Max‑heap: parent ≥ children
• Min‑heap: parent ≤ children

Because the tree is complete, it can be stored in an array without explicit pointers.

5.1 Building a max‑heap (bottom‑up heapify)

void heapify(int a[], int n, int i){
    int largest = i, l = 2*i, r = 2*i+1;
    if(l<=n && a[l] > a[largest]) largest = l;
    if(r<=n && a[r] > a[largest]) largest = r;
    if(largest != i){
        swap(&a[i], &a[largest]);
        heapify(a, n, largest);
    }
}
void buildMaxHeap(int a[], int n){
    for(int i=n/2; i>=1; --i) heapify(a,n,i);
}

Example data: 12, 9, 1, 13, 16, 24, 21, 5

Step‑by‑step heapify (visual after each heapify call)

Figure 11 – Partial max‑heap after fixing subtree rooted at index 4

Subsequent calls produce the final max‑heap:

Figure 12 – Final max‑heap (array representation)

5.2 Heap‑Sort

1. Build max‑heap.
2. Swap root with last element, reduce heap size, heapify root.
3. Repeat until size = 1.

void heapSort(int a[], int n){
    buildMaxHeap(a,n);
    for(int i=n; i>1; --i){
        swap(&a[1], &a[i]);   // move max to end
        heapify(a,i-1,1);     // restore heap on reduced size
    }
}

Running heap‑sort on the example yields 1 5 9 12 13 16 21 24 (ascending).

6. Comparison of Tree Types

| Feature          | Binary Tree | BST | AVL Tree | Binary Heap |
|------------------|-------------|-----|----------|-------------|
| Ordering         | None        | Yes (in‑order) | Yes (balanced) | Yes (heap property) |
| Shape constraint | None        | None | Height‑balanced | Complete |
| Search complexity| O(n)        | O(log n) avg | O(log n) worst | O(1) for max/min |
| Insert/Delete    | O(1) (linked) / O(n) (array) | O(log n) avg | O(log n) | O(log n) |
| Typical use      | Hierarchical data | Dictionaries, sets | DB indexes | Priority queue, heap‑sort |

7. In the real world

• Daraz uses a binary search tree (or balanced variant) to store product IDs. When a user searches “smartphone”, the BST enables O(log n) lookup of the matching SKU, speeding up the search results page.
• NTC & Ncell schedule data packets using a max‑heap priority queue. Packets with higher QoS priority are placed near the root; the scheduler extracts the max‑priority packet in O(log n) time, ensuring low‑latency voice calls.
• eSewa processes transaction batches with heap‑sort to generate a chronological settlement list. After inserting all transaction timestamps into a max‑heap, heap‑sort produces a sorted list used for daily reconciliation with banks.

Worked real‑world trace: A bank’s loan‑approval system stores pending applications in a min‑heap keyed by “risk score”. The smallest score (least risky) is always at the root, so the system can instantly fetch the safest loan to approve first, mirroring the heap‑extract‑min operation shown earlier.

8. Exam tip

• Drawing trees: Always start from the root, place left child to the left, right child to the right, and keep levels aligned. For reconstruction questions, write down the inorder and preorder sequences, then recursively pick the root (first preorder element) and split inorder accordingly.
• BST operations: Memorise the three deletion cases; sketch a tiny “case‑chart” before writing code.
• Traversals: Remember the order mnemonics – In‑order = Left‑Root‑Right, Pre‑order = Root‑Left‑Right, Post‑order = Left‑Right‑Root. For level‑order, draw a queue beside the tree and simulate enqueues/dequeues.
• Heap‑sort: Write the array indices (starting at 1) in the margin; during heapify, mark which indices are compared. This prevents off‑by‑one errors that cost marks.
• Time‑complexity: Be ready to state O(log n) for balanced BST search/insert/delete, O(n log n) for heap‑sort, and O(n) for traversals.

Good luck!