</>EmbeddedInterview

What are binary search trees, and why use a balanced tree?

MediumData Structures & Algorithms

Short answer: In a binary search tree (BST), every node's left subtree has smaller keys and its right subtree larger keys, so search, insert and delete follow one path from the root: O(height). If keys arrive in sorted order, a plain BST degenerates into a linked list (height n, O(n) operations). Self-balancing trees (red-black, AVL) restructure with rotations to keep the height O(log n) in the worst case, and they keep keys in order (unlike hash tables), supporting in-order traversal and range queries.

#include <stdio.h>
#include <stddef.h>

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

struct tnode *bst_insert(struct tnode *root, struct tnode *n)    /* n comes from a pool */
{
    struct tnode **p = &root;
    while (*p) p = (n->key < (*p)->key) ? &(*p)->left : &(*p)->right;   /* iterative: no recursion */
    n->left = n->right = NULL;
    *p = n;
    return root;
}

struct tnode *bst_find(struct tnode *r, int key)
{
    while (r && r->key != key) r = (key < r->key) ? r->left : r->right;
    return r;
}

static void inorder(const struct tnode *r) { if (!r) return; inorder(r->left); printf("%d ", r->key); inorder(r->right); }

int main(void)
{
    static struct tnode pool[6];
    int keys[] = { 50, 30, 70, 20, 40, 60 };
    struct tnode *root = NULL;
    for (int i = 0; i < 6; i++) { pool[i].key = keys[i]; root = bst_insert(root, &pool[i]); }
    inorder(root); printf("| found 40: %s\n", bst_find(root, 40) ? "yes" : "no");   /* 20 30 40 50 60 70 | yes */
    return 0;
}

Where balanced trees appear in systems software

  • Linux: red-black trees (rbtree) for the CFS/EEVDF run queue, hrtimers, virtual memory areas (now a maple tree), epoll; Zephyr's scalable scheduler queue.
  • Interval trees for overlapping ranges (memory regions, IOMMU mappings).
  • B-trees and B+ trees for filesystems and databases on flash (high fan-out, fewer reads).

Traversals: in-order (sorted output), pre-order (copy/serialise a tree), post-order (free a tree), level-order (BFS with a queue). For embedded code, avoid deep recursion on unbalanced trees; use iterative traversals with an explicit stack.