Binary Search Tree (BST)
Last updated
A binary search tree keeps its values in sorted order: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. To insert or find a value you start at the root and repeatedly go left or right depending on the comparison, so each step halves the search space. Press play above to watch values placed by comparison and a search walk down the tree.
On a balanced tree these operations run in O(log n) time. The catch: inserting already-sorted data makes the tree degenerate into a linked list with O(n) operations - which is exactly why self-balancing variants like AVL and red-black trees exist.
Time & space complexity
| Operation | Balanced | Worst case (skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Space | O(n) | O(n) |
Step by step (insert)
| Step | What happens |
|---|---|
| 1 | If the tree is empty, the new value becomes the root. |
| 2 | Otherwise start at the root. |
| 3 | If the value is smaller, go to the left child; if larger, go right. |
| 4 | Repeat until you reach an empty spot. |
| 5 | Attach the new value as a leaf there. |
Worked example
Inserting [5, 3, 8, 1, 4] into an empty tree, one value at a time:
| Insert | Path taken | Action |
|---|---|---|
5 | - | Tree is empty, so 5 becomes the root. |
3 | 5 | 3 < 5, go left; the spot is empty, attach 3 as the left child of 5. |
8 | 5 | 8 > 5, go right; the spot is empty, attach 8 as the right child of 5. |
1 | 5 -> 3 | 1 < 5 go left, then 1 < 3 go left; attach 1 as the left child of 3. |
4 | 5 -> 3 | 4 < 5 go left, then 4 > 3 go right; attach 4 as the right child of 3. |
When to use a binary search tree
| Use it when | Avoid it when |
|---|---|
| You need sorted order plus fast lookups, and insertions arrive in random order. | Your data arrives already sorted - an unbalanced BST degrades to O(n) per operation. |
| You want in-order traversal to yield values in sorted sequence for free. | You only need membership tests and no ordering - a hash table gives O(1) average lookups. |
| You need range queries or the successor/predecessor of a key. | You need guaranteed O(log n) bounds - reach for a self-balancing AVL or red-black tree instead. |
| The dataset changes often and a static sorted array would be costly to update. | The dataset is fixed and read-only - a sorted array with binary search is simpler and cache-friendly. |
Binary Search Tree code
A clean, runnable Binary Search Tree implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Binary Search Tree code in Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Binary Search Tree code in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Binary Search Tree code in Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Binary Search Tree code in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Binary Search Tree code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}Binary Search Tree FAQ
What is the time complexity of a binary search tree?
Search, insert, and delete are
O(log n) on a balanced tree, because each comparison discards half the remaining nodes. In the worst case - a tree skewed into a chain by sorted insertions - they degrade to O(n).What is the difference between a binary tree and a binary search tree?
A binary tree is any tree where each node has at most two children, with no ordering rule. A binary search tree adds the invariant that left-subtree values are smaller and right-subtree values are larger than the node, which is what enables fast searching.
Why can a binary search tree become slow?
If values are inserted in sorted (or reverse-sorted) order, every new node goes to the same side, producing a tall, skewed tree that behaves like a linked list -
O(n) per operation. Self-balancing trees (AVL, red-black) rotate nodes to prevent this.What is the difference between a binary search tree and a hash table?
A hash table gives
O(1) average lookups but stores keys in no particular order, so it cannot answer range or successor queries. A binary search tree is slightly slower at O(log n) but keeps keys ordered, letting you traverse them in sorted order and find nearest values. Choose a BST when order matters and a hash table when you only need membership tests.When should I use a self-balancing tree instead of a plain BST?
Use a self-balancing tree (AVL, red-black) whenever you cannot control the insertion order and need guaranteed
O(log n) performance. A plain BST is fine for teaching, for small datasets, or when keys arrive in random order, but it offers no protection against the skewed worst case.Does an in-order traversal of a BST return sorted values?
Yes. Visiting the left subtree, then the node, then the right subtree yields the keys in ascending order, which follows directly from the BST invariant. A common mistake is expecting the same from a plain binary tree - without the ordering rule, in-order traversal produces no meaningful sequence.
Related resources
More visualizations
