What is a binary search tree used for?

It's used to store ordered data so that search, insertion, and deletion can all be performed in roughly logarithmic time, which is far faster than scanning an unsorted list.

What's the difference between a BST and a balanced BST?

A plain BST has no guarantee about its shape and can become as slow as a linked list in the worst case. A balanced BST, like an AVL or red-black tree, adds rules that keep the tree roughly the same height on both sides, guaranteeing O(log n) operations.

How does deletion work in a BST?

Deleting a leaf node is trivial, deleting a node with one child means promoting that child, and deleting a node with two children typically involves replacing it with its in-order successor (or predecessor) and then deleting that node instead.

Is a binary search tree the same as a binary tree?

No. A binary tree is any tree where nodes have at most two children, with no ordering requirement. A binary search tree is a binary tree that additionally enforces the left-smaller, right-larger ordering invariant.

When should I avoid using a BST?

If your data arrives already sorted and you use an unbalanced BST, performance degrades to O(n). In that case, use a self-balancing tree, a sorted array with binary search for read-heavy workloads, or a hash table if ordering isn't required.

Programming

Binary Search Tree

IntermediateConcept4.4K learners

A binary search tree (BST) is a node-based data structure in which each node has at most two children, and every node's left subtree contains only values less than the node while its right subtree contains only values greater, enabling…

#BinarySearchTree #Programming#Concept#Intermediate#DataStructures #LinkedList #HashTable #BigONotation #SoftwareDevelopment#Glossary#SkillVeris

Definition

Overview

A binary search tree is one of the foundational data structures taught alongside linked lists and hash tables, because it demonstrates how ordering data hierarchically can make search dramatically faster than scanning a flat list. Each node stores a key, an optional value, and pointers to a left and right child. The invariant that left descendants are smaller and right descendants are larger means an in-order traversal visits nodes in sorted order, and a lookup can discard half the remaining tree at each step, similar in spirit to binary search over a sorted array. On a balanced tree, search, insertion, and deletion all run in O(log n) time, which is why understanding Big O Notation matters when reasoning about BST performance. The catch is that a plain BST is not self-balancing: inserting already-sorted data can degrade it into a linked list with O(n) operations. This is why real-world systems typically use self-balancing variants (AVL trees, red-black trees) or B-trees for on-disk indexes, which apply the same ordering principle with extra bookkeeping to keep the tree shallow. BSTs underpin many higher-level structures: ordered maps and sets in standard libraries, database indexes, and expression parsers. They're also a frequent whiteboard interview topic because implementing insert, search, delete, and traversal correctly requires careful handling of recursion and edge cases like deleting a node with two children. Because pointer-chasing through tree nodes involves scattered memory access, BSTs can be slower in practice than array-based structures for small datasets despite better asymptotic complexity — a nuance worth understanding before defaulting to a tree for every ordered-data problem.

Key Concepts

Left-subtree-smaller, right-subtree-larger ordering invariant at every node
O(log n) average-case search, insert, and delete on a balanced tree
In-order traversal yields keys in sorted order
Degrades to O(n) worst case when inserted data is already sorted (unbalanced)
Foundation for self-balancing variants like AVL and red-black trees
Recursive definition makes insert/search/delete naturally recursive algorithms
Supports efficient range queries (min, max, successor, predecessor)

Use Cases

Implementing ordered maps and sets in standard libraries

Database and filesystem indexing (via balanced variants like B-trees)

Autocomplete and dictionary lookups

Expression parsing and evaluation trees in compilers

Priority-based scheduling when combined with balancing

Teaching recursion, pointers, and algorithmic complexity in CS courses

Coding-interview problems on tree traversal and manipulation

Frequently Asked Questions

From the Blog

Programming

Python File I/O: Reading and Writing Files

Almost every real Python program reads or writes files — logs, configs, CSVs, JSON, reports. This guide covers text files, CSV, JSON, binary files, and the modern pathlib approach, with best practices for safe file handling.

How to Build a Developer Portfolio That Gets You Hired

A developer portfolio is your most powerful job-search tool — more important than your degree, and often more persuasive than your resume. This guide explains what to build, how to present it, and how to make recruiters stop scrolling.

LinkedIn Tips for Developers: Turn Your Profile Into an Inbound Machine

Most developers treat LinkedIn as an online CV and wonder why recruiters don't reach out. This guide explains how to optimise your profile for recruiter search, what to post to build visibility, and how to use LinkedIn to land interviews without cold-applying.

RAG Explained: Retrieval-Augmented Generation

RAG is how you give an LLM access to your own private data without training a new model. This guide explains the full pipeline — chunking, embeddings, vector search, and augmented generation — with a working Python example using open-source tools.