Binary Search Tree · learnDataStructures

Binary Search Tree (BST)

What is a BST?

A Binary Search Tree stores distinct integers (here we enforce 0..10000) in a binary tree so that search is fast. It obeys one rule—the BST invariant:

For any node with key k, every key in its left subtree is < k, and every key in its right subtree is > k. The rule holds recursively for all subtrees.

How insert/search/delete work (high level)

Search: compare with current node; go left if smaller, right if larger, stop if equal.
Insert: perform a search; when you fall off a null child, attach a new node there (we reject duplicates).
Delete:
- 0 children: remove the node.
- 1 child: splice the child up.
- 2 children: swap with the successor (minimum in right subtree), then delete that successor.

Traversals (how to visit every node)

Inorder (Left, Node, Right): on a BST, this yields sorted ascending order.
Preorder (Node, Left, Right): root first—useful for copying or prefix expressions.
Postorder (Left, Right, Node): children first—useful for deletes/evaluations.
Level-order (BFS): layer by layer using a queue.

What is the k-th smallest?

It means “the element at rank k in sorted order”, with k=1 being the smallest. We compute this by an iterative inorder walk (our baseline is O(k+h))—with an augmentation that stores subtree_size at each node you can do it in O(h) (≈O(log n) on balanced trees).

Balanced vs perfectly balanced

Perfectly balanced: all leaves are at the same level.
Balanced (informally): no path is much longer than another; height is O(log n).
Plain BSTs can degenerate to a chain (height n) if you insert sorted data. Balancing schemes (AVL, Red–Black) prevent this; we intentionally use an unbalanced BST here.
“Root is the median” is true only if you build the tree by repeatedly choosing medians (e.g., from a sorted array); normal insert order does not guarantee that.

Complexities (unbalanced BST)

Operation	Average	Worst	Notes
search / insert / delete	O(log n)	O(n)	Height `h` dominates
min / max	O(h)	O(n)	Follow extreme left/right
k-th smallest	O(k+h)	O(n)	With subtree sizes: `O(h)`
traversals	O(n)		Visit each node once

Implementations & Complexity

Implementations by Language (choose a variant)

Python

BST (recursive)

class Node:
    __slots__ = ("key","left","right")
    def __init__(self, key): self.key=key; self.left=None; self.right=None

def search(u, x):
    if not u: return None
    if x == u.key: return u
    return search(u.left, x) if x < u.key else search(u.right, x)

def insert(u, x):
    if not u: return Node(x)
    if x == u.key: return u
    if x < u.key: u.left = insert(u.left, x)
    else:         u.right = insert(u.right, x)
    return u

def delete(u, x):
    if not u: return None
    if x < u.key: u.left = delete(u.left, x)
    elif x > u.key: u.right = delete(u.right, x)
    else:
        if not u.left: return u.right
        if not u.right: return u.left
        s = u.right
        while s.left: s = s.left
        u.key = s.key
        u.right = delete(u.right, s.key)
    return u

BST (iterative)

def search_it(u, x):
    while u:
        if x == u.key: return u
        u = u.left if x < u.key else u.right
    return None

def insert_it(root, x):
    if not root: return Node(x)
    p = None; u = root
    while u:
        p = u
        if x == u.key: return root
        u = u.left if x < u.key else u.right
    if x < p.key: p.left = Node(x)
    else: p.right = Node(x)
    return root

def delete_it(root, x):
    p = None; u = root
    while u and u.key != x:
        p = u; u = u.left if x < u.key else u.right
    if not u: return root
    if u.left and u.right:
        ps = u; s = u.right
        while s.left: ps, s = s, s.left
        u.key, s.key = s.key, u.key
        p, u = ps, s
    child = u.left or u.right
    if not p: return child
    if p.left is u: p.left = child
    else: p.right = child
    return root

Ordered list + bisect (library)

from bisect import bisect_left

class OrderedSet:
    def __init__(self): self.a = []     # sorted list
    def has(self, x):
        i = bisect_left(self.a, x)
        return i < len(self.a) and self.a[i] == x    # O(log n)
    def insert(self, x):
        i = bisect_left(self.a, x)
        if i == len(self.a) or self.a[i] != x:
            self.a.insert(i, x)                      # O(n) shift
    def delete(self, x):
        i = bisect_left(self.a, x)
        if i < len(self.a) and self.a[i] == x:
            self.a.pop(i)                            # O(n) shift
    def kth(self, k): return self.a[k-1]             # O(1)

Java

BST (recursive)

class Node { int key; Node left, right; Node(int k){key=k;} }

static Node search(Node u, int x){
  if(u==null) return null;
  if(x==u.key) return u;
  return x<u.key ? search(u.left,x) : search(u.right,x);
}
static Node insert(Node u, int x){
  if(u==null) return new Node(x);
  if(x==u.key) return u;
  if(x<u.key) u.left = insert(u.left,x);
  else u.right = insert(u.right,x);
  return u;
}
static Node delete(Node u, int x){
  if(u==null) return null;
  if(x<u.key) u.left = delete(u.left,x);
  else if(x>u.key) u.right = delete(u.right,x);
  else {
    if(u.left==null) return u.right;
    if(u.right==null) return u.left;
    Node s=u.right;
    while(s.left!=null) s=s.left;
    u.key=s.key;
    u.right=delete(u.right,s.key);
  }
  return u;
}

BST (iterative)

static Node searchIt(Node u, int x){
  while(u!=null){
    if(x==u.key) return u;
    u = (x<u.key)?u.left:u.right;
  }
  return null;
}
static Node insertIt(Node root, int x){
  if(root==null) return new Node(x);
  Node p=null, u=root;
  while(u!=null){
    p=u;
    if(x==u.key) return root;
    u = (x<u.key)?u.left:u.right;
  }
  if(x<p.key) p.left=new Node(x); else p.right=new Node(x);
  return root;
}
static Node deleteIt(Node root, int x){
  Node p=null, u=root;
  while(u!=null && u.key!=x){ p=u; u=(x<u.key)?u.left:u.right; }
  if(u==null) return root;
  if(u.left!=null && u.right!=null){
    Node ps=u, s=u.right;
    while(s.left!=null){ ps=s; s=s.left; }
    int tmp=u.key; u.key=s.key; s.key=tmp; p=ps; u=s;
  }
  Node child=(u.left!=null)?u.left:u.right;
  if(p==null) return child;
  if(p.left==u) p.left=child; else p.right=child;
  return root;
}

ArrayList + Collections.binarySearch (library)

import java.util.*;

class OrderedSet {
  private final ArrayList<Integer> a = new ArrayList<>();
  boolean has(int x){
    int i = Collections.binarySearch(a, x);
    return i >= 0;                         // O(log n)
  }
  void insert(int x){
    int i = Collections.binarySearch(a, x);
    if(i < 0) a.add(-i-1, x);              // O(n) shift
  }
  void delete(int x){
    int i = Collections.binarySearch(a, x);
    if(i >= 0) a.remove(i);                // O(n) shift
  }
  int kth(int k){ return a.get(k-1); }     // O(1)
}

C++

BST (recursive)

struct Node{ int key; Node* left=nullptr; Node* right=nullptr; Node(int k):key(k){} };

Node* search(Node* u, int x){
  if(!u) return nullptr;
  if(x==u->key) return u;
  return (x<u->key) ? search(u->left,x) : search(u->right,x);
}
Node* insert(Node* u, int x){
  if(!u) return new Node(x);
  if(x==u->key) return u;
  if(x<u->key) u->left = insert(u->left,x);
  else          u->right = insert(u->right,x);
  return u;
}
Node* deleteNode(Node* u, int x){
  if(!u) return nullptr;
  if(x<u->key) u->left = deleteNode(u->left,x);
  else if(x>u->key) u->right = deleteNode(u->right,x);
  else{
    if(!u->left){ Node* r=u->right; delete u; return r; }
    if(!u->right){ Node* l=u->left;  delete u; return l; }
    Node* s=u->right; while(s->left) s=s->left;
    u->key=s->key; u->right=deleteNode(u->right,s->key);
  }
  return u;
}

BST (iterative)

Node* searchIt(Node* u, int x){
  while(u){
    if(x==u->key) return u;
    u = (x<u->key)?u->left:u->right;
  }
  return nullptr;
}
Node* insertIt(Node* root, int x){
  if(!root) return new Node(x);
  Node *p=nullptr, *u=root;
  while(u){
    p=u;
    if(x==u->key) return root;
    u = (x<u->key)?u->left:u->right;
  }
  if(x<p->key) p->left=new Node(x); else p->right=new Node(x);
  return root;
}
Node* deleteIt(Node* root, int x){
  Node *p=nullptr, *u=root;
  while(u && u->key!=x){ p=u; u=(x<u->key)?u->left:u->right; }
  if(!u) return root;
  if(u->left && u->right){
    Node *ps=u, *s=u->right;
    while(s->left){ ps=s; s=s->left; }
    std::swap(u->key, s->key); p=ps; u=s;
  }
  Node* child = u->left ? u->left : u->right;
  if(!p){ delete u; return child; }
  if(p->left==u) p->left=child; else p->right=child;
  delete u; return root;
}

std::vector + std::lower_bound (library)

#include <vector>
#include <algorithm>

struct OrderedSet {
  std::vector<int> a;                     
  bool has(int x) const {
    auto it = std::lower_bound(a.begin(), a.end(), x);
    return it != a.end() && *it == x;     // O(log n)
  }
  void insert(int x){
    auto it = std::lower_bound(a.begin(), a.end(), x);
    if(it==a.end() || *it!=x) a.insert(it, x);  // O(n) shift
  }
  void erase(int x){
    auto it = std::lower_bound(a.begin(), a.end(), x);
    if(it!=a.end() && *it==x) a.erase(it);     // O(n) shift
  }
  int kth(int k) const { return a[k-1]; }       // O(1)
};

Concept Checks

State and use the BST invariant to justify each step of insert/search.
Delete nodes in the three cases (0/1/2 children) and show the invariant remains true.
Run inorder on your tree. Why is the output sorted?
Give an insertion order that creates a chain of height n-1 (e.g., sorted ascending).
Implement k-th smallest via iterative inorder; how would subtree sizes change the complexity?

learnDataStructures

Binary Search Tree (BST)

What is a BST?

How insert/search/delete work (high level)

Traversals (how to visit every node)

What is the k-th smallest?

Balanced vs perfectly balanced

Complexities (unbalanced BST)

BST — reference & pseudocode

Pseudocode (insert, search, delete, min/max, k-th, traversals)

Interactive BST simulator

Implementations & Complexity

Implementations by Language (choose a variant)

Python

Java

C++

Concept Checks