Trees and Binary Search Trees

A tree is a hierarchical structure with a root and child nodes. In a binary tree each node has at most two children.

Terminology

Root, parent, child, leaf (no children), sibling, depth (edges from the root), height (longest path to a leaf), degree (number of children).

Binary Search Tree

In a BST: left subtree < node < right subtree. An inorder traversal visits keys in sorted order.

BST built from 50, 30, 70, 20, 40, 60, 80 (left < node < right)

#include <stdio.h>
#include <stdlib.h>

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

struct Node* insert(struct Node *r, int k) {
    if (!r) {
        r = malloc(sizeof(struct Node));
        r->key = k; r->left = r->right = NULL;
    } else if (k < r->key) r->left = insert(r->left, k);
    else                   r->right = insert(r->right, k);
    return r;
}
void inorder(struct Node *r)  { if (r) { inorder(r->left); printf("%d ", r->key); inorder(r->right); } }
void preorder(struct Node *r) { if (r) { printf("%d ", r->key); preorder(r->left); preorder(r->right); } }
void postorder(struct Node *r){ if (r) { postorder(r->left); postorder(r->right); printf("%d ", r->key); } }

int main() {
    struct Node *root = NULL;
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    printf("Inorder:   "); inorder(root);   printf("\n");
    printf("Preorder:  "); preorder(root);  printf("\n");
    printf("Postorder: "); postorder(root); printf("\n");
    return 0;
}

Inorder: 20 30 40 50 60 70 80 Preorder: 50 30 20 40 70 60 80 Postorder: 20 40 30 60 80 70 50

Balanced Trees

A BST built from sorted input degenerates into a list (O(n) search). AVL trees keep |height(left) − height(right)| ≤ 1 using rotations (LL, RR, LR, RL), which guarantees O(log n). Red-black trees and B-trees are other self-balancing trees.

Heap

A complete binary tree where each parent ≥ its children (max-heap) or ≤ them (min-heap). It's used for priority queues and heap sort.

Track your progress through the Data Structures course

← Prev Next →