Data Structures
Binary Search Tree (BST)
Difficulty: Intermediate
Run an inorder traversal on a Binary Search Tree (BST) of any size and the keys come out sorted, in O(n) time and O(h) space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what...
Binary Search Tree (BST)
Run an inorder traversal on a Binary Search Tree (BST) of any size and the keys come out sorted, in O(n) time and O(h) space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what turns a generic binary tree into a logarithmic-time search container that powers Java's TreeMap, C++ std::map, and the conceptual model behind every database index.
This lesson covers the BST property (left subtree keys less than the node, right subtree keys greater), search and insert that follow the invariant, the three deletion cases (leaf, one child, two children resolved by inorder successor or predecessor), and the validation problem that interviewers love because the naive node.left.val < node.val check is wrong. You will also analyze the gap between the balanced O(log n) and the degenerate O(n) chain that motivates the next lesson.
In Trees: Binary Tree Fundamentals, you implemented preorder, inorder, postorder, and level-order traversals; the BST property is what makes inorder special, because it now produces sorted output for free.
Next, Balanced BST (AVL / Red-Black) addresses the elephant in the room: an unlucky insertion order can degrade a BST to a linked list, and self-balancing rotations are the fix.
Prerequisites:
Trees: Binary Tree FundamentalsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
State the BST property and verify whether a given binary tree is a valid BST.
Implement search, insert, and delete operations on a BST in both JavaScript and Python.
Explain the three cases of BST deletion (leaf, one child, two children) and why the in-order successor/predecessor maintains the BST property.
Trace in-order traversal of a BST and explain why it produces sorted output.
Analyze time complexity of BST operations for balanced (O(log n)) and degenerate (O(n)) cases.
Identify when to use a BST versus a hash map and describe real-world BST applications.
Why This Matters
01
BSTs are one of the most frequently tested data structures in technical interviews, appearing in problems like 'validate BST,' 'kth smallest element,' 'lowest common ancestor,' and 'convert sorted array to BST.'
02
The BST property -- left < root < right -- makes in-order traversal produce sorted output in O(n), which is the conceptual foundation for understanding how databases maintain ordered indexes efficiently.
03
Understanding BSTs is a prerequisite for balanced trees (AVL, Red-Black), which guarantee O(log n) worst-case performance and power standard library implementations like Java's TreeMap and C++'s std::map.
04
The three deletion cases (leaf, one child, two children with in-order successor) develop crucial pointer-manipulation skills that transfer to many tree and graph problems.
Key Terms
8 terms you'll encounter in this lesson
BST Property
For every node in a Binary Search Tree, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater. This must hold recursively for all nodes.
In-order Successor
The node with the smallest value that is larger than a given node's value. In a BST, this is the leftmost node in the right subtree. Used during deletion of a node with two children.
In-order Predecessor
The node with the largest value that is smaller than a given node's value. In a BST, this is the rightmost node in the left subtree.
Degenerate BST
A BST where every node has only one child, forming a shape that looks like a linked list. All operations become O(n) instead of O(log n). This happens when elements are inserted in sorted order.
Balanced BST
A BST where the height is O(log n), ensuring all operations run in O(log n) time. AVL trees and Red-Black trees are self-balancing BSTs that maintain this property automatically.
Floor
The largest key in the BST that is less than or equal to a given value. Returns null if no such key exists.
Ceiling
The smallest key in the BST that is greater than or equal to a given value. Returns null if no such key exists.
Range Query
Finding all keys in a BST that fall within a given range [lo, hi]. Achievable in O(h + k) time where h is tree height and k is the number of keys in range.
Heads Up
Common misconceptions to watch out for
"BST search is always O(log n)"
O(log n) only holds when the tree is balanced. A degenerate BST (shaped like a linked list) gives O(n) search. This is why self-balancing BSTs (AVL, Red-Black) exist -- they guarantee O(log n) by rebalancing after each insert/delete.
"Deleting a node with two children requires rebuilding the subtree"
You only need to replace the deleted node's value with its in-order successor (or predecessor), then delete the successor node (which has at most one child). No subtree reconstruction is needed -- just two pointer adjustments.
"A BST and a heap are interchangeable"
A BST maintains full ordering (left < root < right) enabling O(log n) search for any value. A heap maintains partial ordering (parent <= children) enabling O(1) access to the min/max only. Searching for an arbitrary value in a heap is O(n).
"In-order traversal of any binary tree gives sorted output"
In-order traversal gives sorted output only for a valid BST. For an arbitrary binary tree, in-order traversal visits nodes left-root-right but the values have no ordering guarantee.