A Binary Search Tree (BST) is a binary tree with an ordering rule:
All values in left subtree < node.val
All values in right subtree > node.val
Example:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
For every node, smaller values go left and larger values go right.
1. BST Node
Python
Run
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
2. Search in a BST
To search for a value:
If current node is
None, value does not exist.If current value equals target, return the node.
If target is smaller, move left.
Otherwise, move right.
Python
Run
def search_bst(root, target):
current = root
while current:
if current.val == target:
return current
if target < current.val:
current = current.left
else:
current = current.right
return None
Complexity
For a balanced BST:
Time: O(log n)
Space: O(1)
For a skewed BST:
Time: O(n)
3. Insert into a BST
To insert a value, follow the search path until an empty position is found.
Python
Run
def insert_bst(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return root
Usage:
Python
Run
root = None
for value in [8, 3, 10, 1, 6, 14]:
root = insert_bst(root, value)
Important
The line below is necessary:
Python
Run
root.left = insert_bst(root.left, val)
The returned subtree root must be attached back to the tree.
4. Validate a BST
A common mistake is checking only the immediate children.
This is not enough:
Python
Run
node.left.val < node.val < node.right.val
You must ensure every node follows the valid range inherited from its ancestors.
Example of an invalid BST:
5
/ \
3 7
/
4
4 is less than 5, but it appears inside the right subtree of 5, so the tree is invalid.
Correct solution using bounds
Python
Run
def is_valid_bst(root):
def dfs(node, low, high):
if node is None:
return True
if not (low < node.val < high):
return False
return (
dfs(node.left, low, node.val)
and dfs(node.right, node.val, high)
)
return dfs(root, float("-inf"), float("inf"))
Complexity
Time: O(n)
Space: O(h)
h is the height of the tree.
5. Validate BST Using Inorder Traversal
Important fact:
Inorder traversal of a valid BST produces strictly increasing values.
Python
Run
def is_valid_bst(root):
stack = []
current = root
previous = None
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
if previous is not None and current.val <= previous:
return False
previous = current.val
current = current.right
return True
This is a useful alternative in interviews.
6. Find Minimum and Maximum
Minimum
The minimum value is the leftmost node.
Python
Run
def find_min(root):
if root is None:
return None
current = root
while current.left:
current = current.left
return current.val
Maximum
The maximum value is the rightmost node.
Python
Run
def find_max(root):
if root is None:
return None
current = root
while current.right:
current = current.right
return current.val
7. Delete a Node from a BST
Deletion has three cases.
Case 1: Node is a leaf
5
/
3
Delete 3:
5
Simply remove it.
Case 2: Node has one child
5
/
3
\
4
Delete 3:
5
/
4
Replace the node with its only child.
Case 3: Node has two children
5
/ \
3 7
/ \
6 8
To delete 5, replace it with either:
Inorder successor: smallest value in right subtree
Inorder predecessor: largest value in left subtree
Using the inorder successor, replace 5 with 6.
Complete deletion code
Python
Run
def delete_bst(root, key):
if root is None:
return None
if key < root.val:
root.left = delete_bst(root.left, key)
elif key > root.val:
root.right = delete_bst(root.right, key)
else:
# Case 1: No left child
if root.left is None:
return root.right
# Case 2: No right child
if root.right is None:
return root.left
# Case 3: Two children
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val
root.right = delete_bst(root.right, successor.val)
return root
Complexity
Time: O(h)
Balanced BST:
O(log n)Skewed BST:
O(n)
8. Kth Smallest Element in a BST
Because inorder traversal gives sorted order, the kth visited node is the kth smallest.
Example:
4
/ \
2 6
/ \ / \
1 3 5 7
The 3rd smallest value is 3.
Python
Run
def kth_smallest(root, k):
stack = []
current = root
while True:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1
if k == 0:
return current.val
current = current.right
Complexity
Time:
O(h + k)in the usual traversal analysisSpace:
O(h)
9. Lowest Common Ancestor in a BST
The Lowest Common Ancestor (LCA) is the lowest node that has both target nodes in its subtree.
Example:
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
LCA of 2 and 8 is 6.
LCA of 2 and 4 is 2.
BST solution
Python
Run
def lowest_common_ancestor(root, p, q):
current = root
while current:
if p.val < current.val and q.val < current.val:
current = current.left
elif p.val > current.val and q.val > current.val:
current = current.right
else:
return current
return None
Key idea
If both values are smaller, go left.
If both values are larger, go right.
Otherwise, the current node is the split point and therefore the LCA.
10. Range Sum of BST
Find the sum of all values between low and high.
Python
Run
def range_sum_bst(root, low, high):
if root is None:
return 0
if root.val < low:
return range_sum_bst(root.right, low, high)
if root.val > high:
return range_sum_bst(root.left, low, high)
return (
root.val
+ range_sum_bst(root.left, low, high)
+ range_sum_bst(root.right, low, high)
)
Why skip subtrees?
If root.val < low, every value in the left subtree is also too small.
If root.val > high, every value in the right subtree is also too large.
This is called BST pruning.
11. Convert Sorted Array to Balanced BST
Given:
Python
Run
nums = [-10, -3, 0, 5, 9]
Choose the middle value as the root.
Python
Run
def sorted_array_to_bst(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sorted_array_to_bst(nums[:mid])
root.right = sorted_array_to_bst(nums[mid + 1:])
return root
Better version without slicing
Slicing creates extra arrays, so use indices:
Python
Run
def sorted_array_to_bst(nums):
def build(left, right):
if left > right:
return None
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(nums) - 1)
12. BST Complexity Summary
| Operation | Balanced BST | Skewed BST |
|---|---|---|
| Search | O(log n) |
O(n) |
| Insert | O(log n) |
O(n) |
| Delete | O(log n) |
O(n) |
| Minimum | O(log n) |
O(n) |
| Maximum | O(log n) |
O(n) |
| Traversal | O(n) |
O(n) |
A normal BST does not automatically remain balanced.
Examples of self-balancing BSTs:
AVL Tree
Red-Black Tree
13. Common Interview Patterns
| Question wording | Technique |
|---|---|
| Search for a value | Compare and move left/right |
| Insert a value | Follow BST ordering |
| Validate BST | Bounds or inorder |
| Kth smallest | Inorder traversal |
| Minimum value | Leftmost node |
| Maximum value | Rightmost node |
| Delete node | Three deletion cases |
| LCA in BST | Find split point |
| Sum within range | BST pruning |
| Balanced BST from sorted data | Middle element recursion |
14. Important Mistakes
Mistake 1: Using only local child checks
Incorrect:
Python
Run
if node.left.val < node.val < node.right.val:
...
BST validity depends on all ancestors, not only direct children.
Mistake 2: Forgetting to return updated roots
Always write:
Python
Run
root.left = insert_bst(root.left, val)
and:
Python
Run
return root
Mistake 3: Confusing BST with a normal binary tree
A normal binary tree has no ordering guarantee.
BST-specific shortcuts only work when the ordering rule is valid.
Mistake 4: Mishandling deletion with two children
Use the inorder successor or predecessor, then delete that replacement node.
Practice Questions
Solve these in order:
Search in a Binary Search Tree
Insert into a Binary Search Tree
Validate Binary Search Tree
Minimum Absolute Difference in BST
Kth Smallest Element in a BST
Lowest Common Ancestor of a BST
Delete Node in a BST
Range Sum of BST
Convert Sorted Array to Binary Search Tree
Recover Binary Search Tree
Exam challenge
Implement:
Python
Run
insert_bst(root, 5)
search_bst(root, 7)
find_min(root)
find_max(root)
is_valid_bst(root)
delete_bst(root, 5)
Next topic: Heaps and Priority Queues — min heap, max heap, heapq, top K elements, Kth largest, and merge K sorted lists.
Top comments (0)