A binary tree is a hierarchical structure where each node holds a value and has at most two children, called left and right. The node with no parent is the root. Nodes with no children are leaves. The height of a tree is the number of edges on the longest path from root to leaf; a tree with n nodes has height between O(log n) (balanced) and O(n) (degenerate — essentially a linked list).

struct node {
    int          val;
    struct node *left;
    struct node *right;
};

A binary search tree (BST) adds an ordering invariant: every value in the left subtree is less than the node's value, and every value in the right subtree is greater. This makes search, insert, and delete O(h) where h is the height. On a balanced tree that is O(log n); on a degenerate tree built by inserting sorted data it degrades to O(n).

struct node *search(struct node *n, int val) {
    if (!n || n->val == val) return n;
    return val < n->val ? search(n->left, val) : search(n->right, val);
}

Tree traversals visit nodes in a defined order. In-order (left, root, right) visits a BST in sorted order. Pre-order (root, left, right) is natural for copying or serialising a tree. Post-order (left, right, root) is natural for deletion (free children before the parent).

An unbalanced BST degrades to a linked list in the worst case. Self-balancing variants like the Red-black tree and AVL tree maintain O(log n) height through rotation operations on insert and delete.