Binary Search Tree (BST); Tree Traversals; AVL Trees

Binary Search Tree (BST)

What is a BST?

A Binary Search Tree (BST) is a binary tree where:

• All nodes in the left subtree have values less than the root
• All nodes in the right subtree have values greater than the root
• Both left and right subtrees are also BSTs

         [50]
        /    \
      [30]    [70]
      /  \   /  \
   [20] [40] [60] [80]

Property: In-order traversal of BST gives sorted sequence.

BST Operations

Insertion

btnode_t *insert_bst(btnode_t *root, int value) {
    if (root == NULL) return new_node(value);

    if (value < root->data) {
        root->left = insert_bst(root->left, value);
    } else if (value > root->data) {
        root->right = insert_bst(root->right, value);
    }
    // if equal, don't insert (no duplicates)
    return root;
}

Search

btnode_t *search_bst(btnode_t *root, int target) {
    if (root == NULL) return NULL;          // not found
    if (root->data == target) return root;  // found

    if (target < root->data) {
        return search_bst(root->left, target);   // go left
    } else {
        return search_bst(root->right, target);  // go right
    }
}

Find Minimum

btnode_t *find_min(btnode_t *root) {
    while (root->left != NULL) root = root->left;
    return root;
}

BST Time Complexity

Skewed tree happens when elements are inserted in sorted order → use AVL Tree or Red-Black Tree.

Tree Traversals

What are Tree Traversals?

Tree traversal means visiting every node exactly once in a specific order.

Types of Tree Traversals

12.1 Inorder Traversal (Left → Root → Right)

void inorder(btnode_t *root) {
    if (root == NULL) return;
    inorder(root->left);       // Visit left subtree
    printf("%d ", root->data); // Visit root
    inorder(root->right);      // Visit right subtree
}

Result for BST: Returns sorted sequence (ascending order).

12.2 Preorder Traversal (Root → Left → Right)

void preorder(btnode_t *root) {
    if (root == NULL) return;
    printf("%d ", root->data); // Visit root FIRST
    preorder(root->left);      // Visit left subtree
    preorder(root->right);     // Visit right subtree
}

Use: Serialize a tree; copy a tree; create prefix expression.

12.3 Postorder Traversal (Left → Right → Root)

void postorder(btnode_t *root) {
    if (root == NULL) return;
    postorder(root->left);      // Visit left subtree
    postorder(root->right);     // Visit right subtree
    printf("%d ", root->data);  // Visit root LAST
}

Use: Delete a tree (delete children before parent); evaluate postfix expression trees.

12.4 Level Order (BFS / Breadth-First)

#include <stdlib.h>

void level_order(btnode_t *root) {
    if (root == NULL) return;

    // Use queue
    btnode_t *queue[100];
    int front = 0, rear = -1;

    queue[++rear] = root;
    while (front <= rear) {
        btnode_t *node = queue[front++];
        printf("%d ", node->data);
        if (node->left) queue[++rear] = node->left;
        if (node->right) queue[++rear] = node->right;
    }
}

Traversal Example

Tree:
         [1]
        /   \
      [2]   [3]
      / \
    [4] [5]

Inorder:   4, 2, 5, 1, 3   (L-Root-R)
Preorder:  1, 2, 4, 5, 3   (Root-L-R)
Postorder: 4, 5, 2, 3, 1   (L-R-Root)
Level:     1, 2, 3, 4, 5   (level by level)

AVL Trees

What is an AVL Tree?

An AVL Tree (named after Adelson-Velsky and Landis, 1962) is a self-balancing BST where:

Balance Factor = Height(left subtree) - Height(right subtree)

• Balance Factor must be -1, 0 or +1 for every node.
• If balance factor is ±2 or more → perform rotation to rebalance.

AVL Rotations

Time Complexity (AVL)

Guaranteed O(log n) unlike BST which can degrade to O(n).