Trees, Binary Trees & BST | Ananta Code Academy

🌳

Tree Fundamentals

Nodes, edges, root, leaf, height, depth — the vocabulary every tree program depends on

Part 1

What is a Tree?

A tree is a non-linear, hierarchical data structure made of nodes connected by edges. Unlike arrays or linked lists (which are linear), a tree branches out — one node can point to many children. Trees model real hierarchies: file systems, HTML DOM, organisation charts, and decision trees.

Key rules: a tree with N nodes has exactly N−1 edges. There is exactly one root node (no parent). Every non-root node has exactly one parent. There are no cycles.

🌳 Anatomy of a Tree — all terminology labelled

Key Tree Terminology

Root

The topmost node — has no parent. Entry point of the tree. Node A above.

Node

Basic unit storing data plus pointers to its children. Every circle in the diagram.

Edge

The link between a parent and a child. A tree of N nodes has exactly N−1 edges.

Leaf

A node with no children. H and I are leaves. Also called external nodes.

Height

Longest path from root to any leaf. Tree above has height 3 (A→B→D→H).

Depth

Distance from the root to a given node. Root has depth 0. Node D has depth 2.

Subtree

Any node plus all its descendants forms a subtree. Node B with D,E,H,I is a subtree.

Degree

Number of children a node has. Node A has degree 2. A leaf has degree 0.

tree types — classified by max children per node

Binary Tree

max 2 children

← each node has at most left and right child

Binary Search Tree

left < root < right

← ordering property enables O(log n) search

N-ary Tree

max N children

← e.g. file system directories

Full Binary

0 or 2 children only

← no node has exactly 1 child

Complete Binary

all levels full except last

← last level filled left to right

Perfect Binary

all leaves at same level

← exactly 2^h − 1 nodes

part 2 — binary tree

🌲

Binary Tree in C

Node struct, dynamic allocation, level-order insert, and all three depth-first traversals with full trace

Part 2

Binary Tree Node Structure

In C, each node is a struct with three fields: the data value, a left pointer to the left child, and a right pointer to the right child. Both child pointers are NULL when there is no child. The entire tree is accessed through a single root pointer. All node creation uses malloc — the tree lives on the heap.

The three classic depth-first traversals visit every node exactly once, differing only in when the current node's data is processed relative to its children: Inorder (Left → Root → Right), Preorder (Root → Left → Right), Postorder (Left → Right → Root). All three are implemented recursively — the recursion naturally mirrors the tree's own recursive structure.

🌲 Binary Tree — used in all three traversal examples below

📘 INORDER (LNR)

4 → 2 → 5 → 1 → 6 → 3 → 7

Left subtree first, then node, then right subtree. Gives sorted output on a BST.

📗 PREORDER (NLR)

1 → 2 → 4 → 5 → 3 → 6 → 7

Node first, then left, then right. Used to copy or serialize a tree.

📙 POSTORDER (LRN)

4 → 5 → 2 → 6 → 7 → 3 → 1

Left, right, then node. Used to delete a tree safely (children before parent).

Complete Binary Tree — C implementation

binary_tree.c

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

/* ── Node struct ── */
typedef struct Node {
    int          data;
    struct Node *left;
    struct Node *right;
} Node;

/* ── Create a new heap node ── */
Node* newNode(int val) {
    Node *n  = malloc(sizeof(Node));
    n->data  = val;
    n->left  = n->right = NULL;
    return n;
}

/* ── INORDER  : Left → Root → Right ── */
void inorder(Node *root) {
    if (root == NULL) return;
    inorder(root->left);          /* recurse left   */
    printf("%d ", root->data);    /* visit node     */
    inorder(root->right);         /* recurse right  */
}

/* ── PREORDER : Root → Left → Right ── */
void preorder(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

/* ── POSTORDER: Left → Right → Root ── */
void postorder(Node *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

/* ── Height: longest path root to leaf ── */
int height(Node *root) {
    if (root == NULL) return 0;
    int lh = height(root->left);
    int rh = height(root->right);
    return 1 + (lh > rh ? lh : rh);
}

/* ── Count all nodes ── */
int countNodes(Node *root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left)
              + countNodes(root->right);
}

/* ── Count leaf nodes ── */
int countLeaves(Node *root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return countLeaves(root->left)
         + countLeaves(root->right);
}

/* ── Free entire tree (postorder delete) ── */
void freeTree(Node *root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    /*  Build the tree manually:
              1
            /   \
           2     3
          / \   / \
         4   5 6   7        */
    Node *root  = newNode(1);
    root->left  = newNode(2);
    root->right = newNode(3);
    root->left->left   = newNode(4);
    root->left->right  = newNode(5);
    root->right->left  = newNode(6);
    root->right->right = newNode(7);

    printf("=== Binary Tree ===\n\n");

    printf("Inorder   (L-N-R): "); inorder(root);   printf("\n");
    printf("Preorder  (N-L-R): "); preorder(root);  printf("\n");
    printf("Postorder (L-R-N): "); postorder(root); printf("\n");

    printf("\nHeight      : %d\n",  height(root));
    printf("Total nodes : %d\n",  countNodes(root));
    printf("Leaf nodes  : %d\n",  countLeaves(root));

    freeTree(root);
    printf("\nTree freed.\n");
    return 0;
}

output

=== Binary Tree ===

Inorder   (L-N-R): 4 2 5 1 6 3 7
Preorder  (N-L-R): 1 2 4 5 3 6 7
Postorder (L-R-N): 4 5 2 6 7 3 1

Height      : 3
Total nodes : 7
Leaf nodes  : 4

Tree freed.

Every recursive tree function has the same shape: check if (root == NULL) return; as the base case, then recurse on root->left and root->right, and process root->data before, between, or after the two recursive calls to get Pre, In, or Postorder respectively. Change the order of those three lines and you change the traversal.

Always free trees with Postorder deletion. freeTree calls itself on left and right children first, then frees the current node. If you freed the root first, you'd lose all pointers to children and leak the entire subtree. Postorder naturally handles children-before-parent — which is exactly what safe deletion requires.

part 3 — binary search tree (bst)

🔍

Binary Search Tree (BST)

Insert · Search · Inorder · Height · Min/Max · Delete — all four operations with step-by-step diagrams

Part 3

The BST Property

A Binary Search Tree is a binary tree with one extra rule — the BST property: for every node N, all values in the left subtree of N are less than N's value, and all values in the right subtree are greater than N's value. This ordering is maintained for every node in the tree, not just the root.

Because of this property, searching for a value takes O(h) time where h is the height — O(log n) for a balanced BST, O(n) worst case (a skewed tree that behaves like a linked list). Insert and delete are also O(h). Inorder traversal of a BST always yields the values in sorted ascending order.

🔍 BST built by inserting: 50, 30, 70, 20, 40, 60, 80

BST insert path visualisation — inserting 45

🔍 Tracing insert(45) — compare at each node, go left or right

Full BST implementation in C

bst.c

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

typedef struct BSTNode {
    int              data;
    struct BSTNode  *left;
    struct BSTNode  *right;
} BSTNode;

/* ── Create node ── */
BSTNode* newNode(int val) {
    BSTNode *n  = malloc(sizeof(BSTNode));
    n->data  = val;
    n->left  = n->right = NULL;
    return n;
}

/* ── INSERT: returns updated root ── */
BSTNode* insert(BSTNode *root, int val) {
    if (root == NULL) return newNode(val);  /* found the slot */
    if (val < root->data)
        root->left  = insert(root->left,  val);  /* go left  */
    else if (val > root->data)
        root->right = insert(root->right, val);  /* go right */
    /* equal: no duplicate inserted */
    return root;
}

/* ── SEARCH: returns node or NULL ── */
BSTNode* search(BSTNode *root, int val) {
    if (root == NULL || root->data == val) return root;
    if (val < root->data) return search(root->left,  val);
    else                   return search(root->right, val);
}

/* ── MIN / MAX ── */
BSTNode* minNode(BSTNode *root) {
    while (root && root->left) root = root->left;
    return root;
}
BSTNode* maxNode(BSTNode *root) {
    while (root && root->right) root = root->right;
    return root;
}

/* ── HEIGHT ── */
int height(BSTNode *root) {
    if (!root) return 0;
    int lh = height(root->left);
    int rh = height(root->right);
    return 1 + (lh > rh ? lh : rh);
}

/* ── DELETE ──
   Three cases:
   1. Node has no children  → just remove it
   2. Node has one child    → replace with that child
   3. Node has two children → replace with inorder successor
      (smallest in right subtree), then delete successor     */
BSTNode* deleteNode(BSTNode *root, int val) {
    if (root == NULL) return NULL;

    if (val < root->data) {
        root->left  = deleteNode(root->left,  val);
    } else if (val > root->data) {
        root->right = deleteNode(root->right, val);
    } else {
        /* Found the node to delete */
        if (root->left == NULL) {          /* case 1 & 2 */
            BSTNode *tmp = root->right;
            free(root); return tmp;
        }
        if (root->right == NULL) {         /* case 2     */
            BSTNode *tmp = root->left;
            free(root); return tmp;
        }
        /* case 3: two children */
        BSTNode *succ = minNode(root->right);
        root->data    = succ->data;
        root->right   = deleteNode(root->right, succ->data);
    }
    return root;
}

/* ── Inorder: sorted output ── */
void inorder(BSTNode *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

/* ── Pretty print tree sideways ── */
void printTree(BSTNode *root, int space) {
    if (!root) return;
    space += 5;
    printTree(root->right, space);
    printf("\n%*s%d\n", space, "", root->data);
    printTree(root->left,  space);
}

int main() {
    BSTNode *root = NULL;

    printf("=== Binary Search Tree ===\n");

    /* Build BST */
    int vals[] = { 50, 30, 70, 20, 40, 60, 80, 45 };
    for (int i = 0; i < 8; i++)
        root = insert(root, vals[i]);

    printf("\nTree (rotated 90°, right branch on top):");
    printTree(root, 0);

    printf("\n\nInorder (sorted): "); inorder(root);
    printf("\nHeight          : %d", height(root));
    printf("\nMin             : %d", minNode(root)->data);
    printf("\nMax             : %d\n", maxNode(root)->data);

    /* Search */
    printf("\n--- Search ---\n");
    int targets[] = { 40, 99 };
    for (int i = 0; i < 2; i++) {
        BSTNode *res = search(root, targets[i]);
        printf("  search(%d): %s\n",
               targets[i], res ? "FOUND" : "NOT FOUND");
    }

    /* Delete */
    printf("\n--- Delete 30 (node with two children) ---\n");
    root = deleteNode(root, 30);
    printf("Inorder after delete: "); inorder(root);
    printf("\n");

    printf("\n--- Delete 20 (leaf node) ---\n");
    root = deleteNode(root, 20);
    printf("Inorder after delete: "); inorder(root);
    printf("\n");

    return 0;
}

output

=== Binary Search Tree ===

Tree (rotated 90°, right branch on top):

          80

     70

          60

50

               45

          40

     30

          20

Inorder (sorted): 20 30 40 45 50 60 70 80
Height          : 4
Min             : 20
Max             : 80

--- Search ---
  search(40): FOUND
  search(99): NOT FOUND

--- Delete 30 (node with two children) ---
Inorder after delete: 20 40 45 50 60 70 80

--- Delete 20 (leaf node) ---
Inorder after delete: 40 45 50 60 70 80

BST delete — three cases every delete must handle

Case 1: Leaf

node

→ NULL

← just free the node, parent pointer set to NULL

Case 2: One child

node

→

child

← bypass node, point parent directly to child

Case 3: Two children

node

→

inorder successor

← copy successor's value, delete successor (case 1 or 2)

Inorder successor

min of right subtree

← go right once, then left as far as possible

BST complexity — height h determines all operation times

O(h)

← best O(log n) balanced, worst O(n) skewed

Insert

O(h)

← traverse to correct leaf position

Delete

O(h)

← find node + find successor = 2× path traversals

Inorder traversal

O(n)

← must visit every node once

Space (stack)

O(h)

← recursive call stack depth = height

BST degenerates to a linked list if you insert sorted data. Inserting 10, 20, 30, 40, 50 in order into a BST produces a tree that goes entirely right — height N, all O(N) operations. This is the worst case. Solutions: AVL trees and Red-Black trees are self-balancing BSTs that keep height O(log n) by rotating nodes after every insert and delete.

Inorder traversal of a BST always produces sorted output. This is directly provable from the BST property: for any node, everything to its left is smaller (printed before it) and everything to its right is larger (printed after). You can use this to check whether a tree is a valid BST — run inorder and verify the output is strictly ascending.

checklist

Tree basics — N nodes, N−1 edges. One root, one parent per non-root. Root has depth 0. Height = longest root-to-leaf path. Leaf = node with no children. Degree = number of children.
Binary Tree node — struct with int data, Node *left, Node *right. Create with malloc. Access whole tree via a single root pointer. Free with postorder deletion.
Inorder (LNR) = sorted output on BST. Preorder (NLR) = copy/serialize a tree. Postorder (LRN) = safe tree deletion. All three: base case if (root==NULL) return, then recurse left+right, process data before/between/after.
BST property — left subtree values < node < right subtree values, at every node. Insert: compare at each node, go left if smaller, right if larger, insert at first NULL. Inorder traversal gives sorted order.
BST Search — O(h). Compare target with node: equal → found, smaller → go left, larger → go right. Returns the node pointer or NULL.
BST Delete — three cases: (1) leaf → free, parent = NULL; (2) one child → bypass, link parent to child; (3) two children → copy inorder successor value (min of right subtree), delete successor recursively.
BST worst case — inserting sorted data makes a skewed tree (linked list), O(n) all operations. Fix with self-balancing trees (AVL, Red-Black). Balanced BST: height O(log n), all ops O(log n).

Trees, Binary Trees& BST in C

What is a Tree?

Key Tree Terminology

Binary Tree Node Structure

The BST Property

Trees, Binary Trees
& BST in C