Trees & Binary Search Trees

Hierarchical data structures that power databases, file systems, and more.

What is a Tree?

A tree is a hierarchical structure with a root node and child nodes, where each child has exactly one parent. Trees model hierarchical relationships — file systems, org charts, and HTML DOM are all trees.

Binary Search Tree (BST)

A BST is a binary tree where, for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property allows searching in O(log n) time on a balanced tree.

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

Traversals

Inorder (Left, Root, Right) gives sorted order in a BST. Preorder (Root, Left, Right) is useful for copying a tree. Postorder (Left, Right, Root) is useful for deleting a tree safely.

🌍 Real-World Use

File explorers (folders inside folders) are trees. Database indexes (B-Trees, a wider version of BST) let databases find a record among millions in just a few steps instead of scanning everything.

💡 Pro Tip

If a BST becomes unbalanced (e.g. you insert sorted data 1,2,3,4,5 in order), it degrades into a linked list with O(n) search — this is exactly why self-balancing trees like AVL and Red-Black Trees exist.

🧪 Quick Self-Test

Check what you just learned — no pressure, just practice.

1. In a BST, where are values smaller than the root stored?

2. Which traversal gives sorted output for a BST?

← Back to all Notes