12. Binary Search Trees (BST)

🧸 ELI5: Imagine organizing your library books on a special shelf: for every book, all books with a smaller title go to its left, and all books with a bigger title go to its right. Now finding any book is like the guessing game (binary search) — go left or right at every shelf.

🌍 Real life: Auto-complete style organized dictionaries. Any "sorted lookup" structure like a phone book organized as a tree instead of a flat list.

📝 Pseudocode:

function insert(node, value):
    if node == null: return newNode(value)
    if value < node.value: node.left = insert(node.left, value)
    else: node.right = insert(node.right, value)
    return node

function search(node, value):
    if node == null: return false
    if node.value == value: return true
    if value < node.value: return search(node.left, value)
    return search(node.right, value)

🐹 Go:

package main

import "fmt"

type BSTNode struct {
	Value       int
	Left, Right *BSTNode
}

func insert(node *BSTNode, value int) *BSTNode {
	if node == nil {
		return &BSTNode{Value: value}
	}
	if value < node.Value {
		node.Left = insert(node.Left, value)
	} else {
		node.Right = insert(node.Right, value)
	}
	return node
}

func search(node *BSTNode, value int) bool {
	if node == nil {
		return false
	}
	if node.Value == value {
		return true
	}
	if value < node.Value {
		return search(node.Left, value)
	}
	return search(node.Right, value)
}

func main() {
	var root *BSTNode
	for _, v := range []int{50, 30, 70, 20, 40} {
		root = insert(root, v)
	}
	fmt.Println(search(root, 40)) // true
	fmt.Println(search(root, 99)) // false
}

🇨 C (deep dive: real-life-c-guide.md §18.3):

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

typedef struct BSTNode {
    int value;
    struct BSTNode *left, *right;
} BSTNode;

BSTNode *bst_insert(BSTNode *node, int value) {
    if (!node) {
        BSTNode *n = malloc(sizeof(BSTNode));
        n->value = value; n->left = n->right = NULL;
        return n;
    }
    if (value < node->value) node->left = bst_insert(node->left, value);
    else                     node->right = bst_insert(node->right, value);
    return node;
}

int bst_search(BSTNode *node, int value) {
    if (!node) return 0;
    if (node->value == value) return 1;
    return value < node->value ? bst_search(node->left, value) : bst_search(node->right, value);
}

void bst_free(BSTNode *node) {
    if (!node) return;
    bst_free(node->left);
    bst_free(node->right);
    free(node);
}

int main(void) {
    BSTNode *root = NULL;
    int values[] = {50, 30, 70, 20, 40};
    for (int i = 0; i < 5; i++) root = bst_insert(root, values[i]);

    printf("%d\n", bst_search(root, 40)); // 1 (true)
    printf("%d\n", bst_search(root, 99)); // 0 (false)
    bst_free(root);
    return 0;
}

⏱️ Complexity: Balanced tree: search/insert/delete = O(log n). Worst case (all books added in sorted order, forming a straight line): O(n) — this is why balanced trees (AVL, Red-Black) exist.