TreesData structureaka BST, ordered binary tree

Binary Search Tree

A binary tree where every left descendant is smaller and every right descendant is larger, giving O(h) ordered search, insert and delete.

▶ Visualize Pattern: Binary Search Practice (3)

Progress

Definition

A binary search tree is a Binary Tree with the BST property: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. That single invariant turns search into a walk from the root: compare, go left or right, repeat. Search, insert and delete all cost O(h) where h is the height.

The catch is that h depends on insertion order. Random insertions give an expected height of about 2 ln n (roughly 1.39 log₂ n), but inserting sorted keys produces a chain of height n. Self-balancing variants such as the AVL Tree and Red-Black Tree add rotations to guarantee h = O(log n).

What a BST offers over a Hash Map is order: inorder traversal lists keys sorted, and operations like minimum, maximum, predecessor, successor, floor, ceiling, rank and range queries all run in O(h).

orderedO(log n) averageinorder sorteddynamic setsuccessor

Intuition

A mental model before the formal terms.

Think of the number-guessing game embedded in pointers. The root is your first guess; "lower" sends you to the left child, "higher" to the right. A well-shaped tree of a million keys is only about 20 levels deep, so each lookup is 20 comparisons.

Deleting is the only awkward operation. Removing a leaf is trivial; removing a node with one child means splicing it out; removing a node with two children means finding its inorder successor (the leftmost node in the right subtree), copying that key up, and deleting the successor instead, which has at most one child.

How it works

Search: start at the root; if the key matches, stop; if it is smaller, move to the left child; otherwise move to the right child. Reaching null means the key is absent.
Insert: search for the key; the null where the search fails is exactly where the new leaf belongs. Duplicates are either rejected or routed consistently (for example to the right).
Delete: locate the node. Zero children: remove it. One child: replace the node by its child. Two children: copy the inorder successor's key into the node and recursively delete the successor from the right subtree.
Min/max: follow left (or right) pointers to the end. Successor of a node with a right subtree is the min of that subtree; otherwise it is the lowest ancestor whose left subtree contains the node.
Validation: pass down an allowed (low, high) range; each node must satisfy low < key < high, and children narrow the range. Checking only immediate children is a classic wrong answer.

Why it works

The BST property holds at every node, so a comparison at any node certifies that the entire other subtree cannot contain the key. Each step descends one level, so the cost is bounded by height.

Insertion at the failed-search position preserves the property because the path taken already satisfied all ancestor constraints. Deletion with the successor preserves it because the successor is the smallest key larger than the deleted key, so it fits between the left subtree and the rest of the right subtree.

Inorder traversal visits left subtree, node, right subtree, and by the invariant everything visited before the node is smaller and everything after is larger, giving sorted order.

Operations

Operation	Description	Cost
search(key)	Walk down comparing at each node.	O(h)
insert(key)	Search to the failed position and attach a leaf.	O(h)
delete(key)	Remove with the 0/1/2-children cases; the two-children case uses the inorder successor.	O(h)
min / max	Follow left / right pointers to the end.	O(h)
successor / predecessor	Next larger / smaller key via subtree min or ancestor walk.	O(h)
floor / ceiling	Largest key ≤ x / smallest key ≥ x by recording candidates while descending.	O(h)
inorder traversal	Yields all keys in sorted order.	O(n)

Recognition

How to tell a problem wants this.

You need a dynamic set with ordered operations: kth smallest, floor/ceiling, predecessor/successor, range count.
The problem gives a BST explicitly ("validate BST", "kth smallest in BST", "LCA in BST") and expects you to exploit the ordering for O(h).
Streaming inserts interleaved with "how many elements are less than x" queries.

“sorted array” → Binary Search “connected groups” → Depth-First Search “binary tree” → Tree Traversal

Interactive demo

Play, step, change the input. ← → and space work too.

Commands — insert N, search N, delete N — separated by commas

Empty tree

1/52Start with an empty BST. Invariant: every node's left subtree holds smaller keys and its right subtree larger keys.

Comparing hereComparison pathNewly insertedFound / successorBeing deleted

PseudocodeLearn Binary Search Tree →

1node = root
2while node: compare key with node.value
3  go left if key < node.value, right if key > node.value
4insert: attach new leaf at the null position reached
5search: found if key == node.value, else not found at null
6delete leaf: unlink it
7delete node with one child: splice child into its place
8delete node with two children: replace with inorder successor (min of right subtree)

Variables

size0

Complexity

access O(log n)

search O(log n)

insert O(log n)

delete O(log n)

Speed

Pseudocode

1insert(node, key):
2  if node is null: return new Node(key)
3  if key < node.key: node.left = insert(node.left, key)
4  else if key > node.key: node.right = insert(node.right, key)
5  return node
6delete(node, key):
7  if node is null: return null
8  if key < node.key: node.left = delete(node.left, key)
9  else if key > node.key: node.right = delete(node.right, key)
10  else if node.left is null: return node.right
11  else if node.right is null: return node.left
12  else: s = min(node.right); node.key = s.key; node.right = delete(node.right, s.key)
13  return node

Implementation

1from typing import Optional
2 
3 
41 · Node definition
5class BSTNode:
6    def __init__(self, key: int) -> None:
7        self.key = key
8        self.left: Optional["BSTNode"] = None
9        self.right: Optional["BSTNode"] = None
10 
11 
12class BST:
13    def __init__(self) -> None:
14        self.root: Optional[BSTNode] = None
15 
162 · Search (iterative descent)
17    def contains(self, key: int) -> bool:
18        cur = self.root
19        while cur is not None:
20            if key == cur.key:
21                return True
22            cur = cur.left if key < cur.key else cur.right
23        return False
24 
253 · Insert (recursive, ignores duplicates)
26    def insert(self, key: int) -> None:
27        def go(n: Optional[BSTNode]) -> BSTNode:
28            if n is None:
29                return BSTNode(key)
30            if key < n.key:
31                n.left = go(n.left)
32            elif key > n.key:
33                n.right = go(n.right)
34            return n
35 
36        self.root = go(self.root)
37 
384 · Delete with three cases (leaf / one child / two children)
39    def remove(self, key: int) -> None:
40        def min_node(n: BSTNode) -> BSTNode:
41            while n.left is not None:
42                n = n.left
43            return n
44 
45        def go(n: Optional[BSTNode], k: int) -> Optional[BSTNode]:
46            if n is None:
47                return None
48            if k < n.key:
49                n.left = go(n.left, k)
50                return n
51            if k > n.key:
52                n.right = go(n.right, k)
53                return n
54            if n.left is None:
55                return n.right
56            if n.right is None:
57                return n.left
58            succ = min_node(n.right)
59            n.key = succ.key
60            n.right = go(n.right, succ.key)
61            return n
62 
63        self.root = go(self.root, key)
64 
655 · Min / max and inorder (sorted output)
66    def min_key(self) -> Optional[int]:
67        cur = self.root
68        if cur is None:
69            return None
70        while cur.left is not None:
71            cur = cur.left
72        return cur.key
73 
74    def max_key(self) -> Optional[int]:
75        cur = self.root
76        if cur is None:
77            return None
78        while cur.right is not None:
79            cur = cur.right
80        return cur.key
81 
82    def inorder(self) -> list[int]:
83        out: list[int] = []
84        stack: list[BSTNode] = []
85        cur = self.root
86        while cur or stack:
87            while cur:
88                stack.append(cur)
89                cur = cur.left
90            cur = stack.pop()
91            out.append(cur.key)
92            cur = cur.right
93        return out

Walkthrough

contains loops with cur = cur.left if key < cur.key else cur.right, a conditional expression.
insert uses a nested go that returns the subtree root; self.root = go(self.root) handles the empty case.
remove nests min_node and go; the two-child case copies the inorder successor key and removes the successor from the right subtree.
min_key/max_key return Optional[int] and check for an empty tree.
inorder is iterative with an explicit stack, so it works on deep trees without raising RecursionError.

Complexity (this implementation)

time O(h) per operation · space O(h) recursion

Recursive insert/remove hit the 1000-frame limit on a skewed tree of a thousand nodes; the iterative inorder does not.

Language notes

Python has no ordered map in the stdlib; bisect on a sorted list or a third-party sortedcontainers.SortedList are the usual substitutes.
Comparison chaining and rich comparisons make keys of any comparable type work with the same code.
Use is None / is not None; a node with key 0 is still truthy but be explicit.

Common mistakes in this language

Writing if not n.left where n.left is a node — fine here, but breaks if nodes define __len__.
Forgetting to reassign n.left = go(n.left) so deletions never take effect.
Deep recursion on sorted input; raise sys.setrecursionlimit or use the iterative alternative.

Language differences that matter here

C++ ships balanced BSTs (std::set, std::map); JS/TS and Python have no ordered map in the standard library.
C++ must delete removed nodes; the others rely on garbage collection once the reference is dropped.
Recursion depth on sorted (skewed) input: Python fails first (~1000), then JS/TS (~10k), then C++ (stack size).
TS forces callers to handle number | undefined from minKey; JS and C++ silently crash on an empty tree unless guarded.

Complexity

Operation	Average	Worst	Note
Access	O(log n)	O(n)	kth element needs subtree sizes for O(h).
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Update	O(log n)	O(n)	Changing a key = delete + insert.
Min / Max	O(log n)	O(n)
Successor / Predecessor	O(log n)	O(n)
Inorder traversal	O(n)	O(n)
Space	O(n)		Average assumes random insertion order (expected height ≈ 1.39 log₂ n). Worst is a chain from sorted input.

Advantages & disadvantages

Advantages

Sorted iteration and order statistics in O(h) — things a hash map cannot do.
Simple to implement; insert and search are a dozen lines.
Expected O(log n) on random input without any balancing code.

Disadvantages

No height guarantee: sorted or adversarial input degrades every operation to O(n).
Slower than a Hash Map for pure key lookup (O(log n) vs O(1) and worse cache behavior).
Deletion logic is fiddly and a common source of bugs.

Use cases

In-memory ordered maps and sets when balancing is added (std::map, Java TreeMap, which use Red-Black Tree).
Order-statistic queries: kth smallest, rank of a key, count in a range.
Interval and event scheduling where you need "the next event after time t".
Teaching vehicle for every balanced tree and for recursive tree algorithms.

Use it when

You need ordered operations (min, max, floor, ceiling, range, kth) on a changing set.
Input order is random or you add balancing; then all operations are O(log n).
Interview problems that explicitly hand you a BST and expect O(h) solutions.

Avoid it when

Only exact-key lookup is needed — a Hash Map is O(1) and simpler.
Insertion order may be sorted or adversarial and you cannot balance — use an AVL Tree or Red-Black Tree instead.
The key set is static — sort an Array once and use Binary Search.

Alternatives

AVL Tree Red-Black Tree Hash Map Skip List Sparse Table

Compare: Hash Map vs Tree Map

Common mistakes

Validating a BST by comparing each node only with its children instead of propagating a (low, high) range.
Forgetting to reassign the returned subtree (node.left = insert(node.left, k)) so inserts silently vanish.
Deleting a two-child node by removing the successor node before copying its key, or deleting the successor from the wrong subtree.
Handling duplicates inconsistently between insert and delete.
Assuming O(log n) in analysis when the input could be sorted.

Interview patterns

Kth smallest via inorder traversal with a counter, stopping early.
LCA in a BST: descend while both keys are on the same side of the current node.
Validate BST with min/max bounds or by checking that inorder output is strictly increasing.
Convert a sorted array to a height-balanced BST by recursing on the middle element.
BST iterator with an explicit stack for O(h) memory next().

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner

Mock interviews

Minimum Size Subarray SumIntermediate
Course ScheduleIntermediate
Number of IslandsIntermediate

Interview problems

Kth Smallest Element in a BSTmedium Validate Binary Search Treemedium Lowest Common Ancestor of a Binary Treemedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related