Binary Search Tree

In Turkish: İkili Arama Ağacı

Updated September 30, 20263 min read

In short

A binary search tree is a binary tree in which each node's left subtree holds smaller values and its right subtree larger ones, enabling fast ordered lookups.

What is a binary search tree?

A binary search tree (BST) is a binary tree, meaning each node has at most two children, with an ordering rule: every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. The rule holds at every node, not just at the root. This ordering is what makes searching fast, because each comparison tells you which whole branch of the tree to ignore.

To search, you start at the root and go left if the target is smaller or right if it is larger, until you find the value or reach an empty spot; inserting follows the same path and adds the new node at that empty spot. Search, insert, and delete each take O(h) time, where h is the height of the tree. In a balanced tree the height is about log2(n), which gives O(log n), but if values are inserted in sorted order the tree becomes one long chain, h grows to n, and every operation degrades to O(n).

It works like a guessing game where every answer is higher or lower: each step rules out an entire branch. Self-balancing BSTs such as AVL trees and red-black trees rearrange nodes with small rotations after inserts and deletes to keep the height at O(log n), and they back sorted collections such as Java's TreeMap and C++'s std::map. An in-order traversal, which visits the left subtree, then the node, then the right subtree, returns every value in sorted order, which makes range queries such as all prices between 10 and 20 efficient.

A BST is often confused with its neighbors. A plain binary tree has no ordering rule at all, and a heap only orders parents relative to their children, which keeps the minimum or maximum on top but doesn't support fast search for arbitrary values. Compared with a hash table, a balanced BST is slower for exact lookups, O(log n) versus O(1) on average, but it keeps keys sorted, which a hash table does not.

At a glance

Smaller values go left and larger ones go right, so each comparison rules out a whole branch.

Key takeaways

Every node's left subtree holds smaller values and its right subtree holds larger ones.
Search, insert, and delete take O(h) time, where h is the height of the tree.
A balanced BST has a height of about log n, so operations are O(log n); a degenerate one is O(n).
Self-balancing variants such as AVL and red-black trees guarantee O(log n) operations.
An in-order traversal visits all values in sorted order in O(n) time.

Example

Searching a binary search tree in Pythonpython

class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def contains(node, target):  # O(h), where h is the height of the tree
    while node is not None and node.value != target:
        # Smaller targets can only be on the left, larger ones on the right
        node = node.left if target < node.value else node.right
    return node is not None

# Root 8: its left subtree (3, 1, 6) is smaller, its right subtree (10) is larger
root = Node(8, Node(3, Node(1), Node(6)), Node(10))
print(contains(root, 6))  # True: 8 -> 3 -> 6
print(contains(root, 7))  # False: 8 -> 3 -> 6 -> empty right child

Readers ask

What is the time complexity of a binary search tree?

Search, insert, and delete take O(h) time, where h is the tree's height. That is O(log n) when the tree is balanced, but it degrades to O(n) when the tree becomes a long chain, for example after inserting values in sorted order.

What is the difference between a binary tree and a binary search tree?

A binary tree only limits each node to at most two children. A binary search tree adds the rule that left descendants are smaller and right descendants are larger, which is what makes fast searching possible.

What is a self-balancing binary search tree?

It is a BST that automatically restructures itself with rotations after inserts and deletes so that its height stays proportional to log n. AVL trees and red-black trees are the best-known examples, and both guarantee O(log n) search, insert, and delete.