Binary Search Tree

treehierarchicalorderedsearch

Press play to start

1function insert(root: BSTNode | null, val: number): BSTNode {
2  if (!root) return new BSTNode(val)
3  if (val < root.val)
4    root.left = insert(root.left, val)
5  else
6    root.right = insert(root.right, val)
7  return root
8}
9function search(root: BSTNode | null, val: number): boolean {
10  if (!root) return false
11  if (root.val === val) return true
12  if (val < root.val) return search(root.left, val)
13  return search(root.right, val)
14}
15// search(root, 60) → true

Step 1/0

Complexity

Best:O(log n)
Average:O(log n)
Worst:O(n)
Space:O(n)

Description

A binary tree where the left subtree contains only nodes with values less than the root, and the right subtree only nodes greater.

When to use

Efficient O(log n) search, insert, delete when balanced. Foundation for sets, maps, and ordered data structures.