Binary Search Trees

BST property, insertion, deletion, and search operations.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

BST Property

A Binary Search Tree maintains: for any node, all values in left subtree < node value < all values in right subtree. This enables O(log n) search/insert/delete on average (O(n) worst case if unbalanced).

Search

Gobst-search.go

13 linesLn 1, Col 1Go

Iterative search following BST property. Go left if smaller, right if larger. O(h) where h is height.

Insertion

Gobst-insertion.go

14 linesLn 1, Col 1Go

Recursive: traverse to null spot, create new node. Return updated node, parent gets new child pointer.

Deletion

Three cases: (1) Leaf: remove directly. (2) One child: replace with child. (3) Two children: find inorder successor (min in right subtree) or predecessor, copy value, delete successor.

Gobst-deletion.go

23 linesLn 1, Col 1Go

Two children: replace with inorder successor (smallest in right subtree), then delete that successor (which has at most one child).

Validate BST

Govalidate-bst-with-bounds.go

10 linesLn 1, Col 1Go

Pass down valid range (min, max). Left subtree max = node.Val, right subtree min = node.Val. Ensures global BST property, not just local.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.