BST Insert and Search
Implement recursive and iterative insert and search, trace the path through the tree for various keys, and analyse worst-case complexity for unbalanced trees.
BST Insert and Search is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The BST Property Defined
A Binary Search Tree satisfies one invariant: for every node, 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 ordering property — maintained across the entire subtree, not just the immediate children — enables O(log n) search, insert, and delete on balanced trees and differentiates a BST from a generic binary tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Valid BST:
# 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
# For node 4: left subtree {1,2,3} < 4 < right subtree {5,6,7}
# This holds recursively for EVERY node in the tree.
print('BST property: left < node < right at every level')Recursive BST Search
BST search works like binary search: compare the target against the current node's value and recurse into the appropriate subtree. If the target equals the current value, return the node. If the target is smaller, go left; if larger, go right. Return null if you reach an empty node. Time complexity is O(h) — O(log n) for balanced, O(n) for skewed trees.
def search_bst(root, val):
if not root:
return None # not found
if root.val == val:
return root # found
if val < root.val:
return search_bst(root.left, val)
else:
return search_bst(root.right, val)
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
result = search_bst(root, 2)
print(result.val if result else 'Not found') # 2
result = search_bst(root, 5)
print(result.val if result else 'Not found') # Not foundIterative BST Search
The iterative search avoids call-stack overhead and is preferred in production code. Use a pointer curr that walks down the tree following left or right based on comparisons. This is a simple while loop with three cases: null (not found), match (found), or adjust direction. Iterative search is also O(h) but uses O(1) space versus O(h) for the recursive version.
def search_bst_iterative(root, val):
curr = root
while curr:
if val == curr.val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None # not found
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
node = search_bst_iterative(root, 3)
print(node.val if node else 'Not found') # 3
print(search_bst_iterative(root, 9)) # NoneRecursive BST Insert
BST insertion finds the correct position by following the same left/right decisions as search, then attaches a new node at the first null position reached. The recursive approach returns the (possibly new) root of each subtree: if the current node is null, return a new TreeNode; otherwise update root.left or root.right with the result of the recursive call. This pattern is clean and common in interview solutions.
def insert_bst(root, val):
if not root:
return TreeNode(val) # create new node here
if val < root.val:
root.left = insert_bst(root.left, val)
elif val > root.val:
root.right = insert_bst(root.right, val)
# val == root.val: duplicate, do nothing (or handle as needed)
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst(root, 1)
root = insert_bst(root, 5)
# Tree is now: 4, left=2(left=1), right=7(left=5)
print(root.right.left.val) # 5Iterative BST Insert
The iterative insert uses a parent pointer to track the last non-null node before reaching the insertion point. Walk down the tree as in search, keeping track of the parent and which direction you went last. When you reach null, attach the new node to the appropriate side of the parent. Always handle the empty-tree edge case (root is null) separately.
def insert_bst_iterative(root, val):
new_node = TreeNode(val)
if not root:
return new_node
curr = root
while True:
if val < curr.val:
if curr.left is None:
curr.left = new_node
break
curr = curr.left
else: # val > curr.val
if curr.right is None:
curr.right = new_node
break
curr = curr.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst_iterative(root, 3)
print(root.left.right.val) # 3Worst-Case BST: Skewed Trees
If you insert a sorted sequence into a BST, you get a skewed tree that degenerates into a linked list. Search, insert, and delete all become O(n). This is why balanced BSTs (AVL trees, Red-Black trees) exist. In interviews, always mention this worst case when asked about BST complexity — saying 'O(log n) average, O(n) worst case for unbalanced trees' demonstrates depth of understanding.
# Inserting 1, 2, 3, 4, 5 into a BST:
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
# This is a right-skewed tree: search is O(n) not O(log n)
root = None
for val in [1, 2, 3, 4, 5]:
root = insert_bst(root, val)
# Verify the skew
node = root
depth = 0
while node:
depth += 1
node = node.right
print(f'Height: {depth}') # 5 = O(n), not O(log n)Finding Minimum and Maximum
In a BST, the minimum value is always the leftmost node (keep going left until you hit null), and the maximum is the rightmost node. These O(h) operations are frequently used as sub-routines in BST deletion (finding the in-order successor) and range queries. Knowing these helpers by heart saves time in interviews.
def find_min(root):
while root.left:
root = root.left
return root
def find_max(root):
while root.right:
root = root.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(9)
print(find_min(root).val) # 1
print(find_max(root).val) # 9In-Order Successor and Predecessor
The in-order successor of a node is the node with the smallest value greater than it. If the node has a right subtree, the successor is find_min(node.right). If it has no right subtree, the successor is the lowest ancestor for which the given node is in the left subtree. Understanding this is critical for BST delete and BST iterator problems.
def inorder_successor(root, p):
successor = None
while root:
if p.val < root.val:
successor = root # possible successor
root = root.left
else:
root = root.right
return successor
def inorder_predecessor(root, p):
predecessor = None
while root:
if p.val > root.val:
predecessor = root # possible predecessor
root = root.right
else:
root = root.left
return predecessor
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
p = root.left # node with val=2
print(inorder_successor(root, p).val) # 3
print(inorder_predecessor(root, p).val) # 1BST Search Complexity Analysis
BST performance depends entirely on tree height. For a balanced BST with n nodes, height is O(log n), giving O(log n) search, insert, and delete. For a skewed BST, height is O(n), giving O(n) for all operations. Python does not have a built-in balanced BST (unlike Java's TreeMap), so you either implement AVL/Red-Black yourself, use sortedcontainers.SortedList, or rely on a heap for priority-queue use cases.
# Python's BST alternatives:
# 1. heapq - min/max heap, O(log n) push/pop
# 2. sortedcontainers.SortedList (third-party, often allowed)
# 3. Manual AVL or Red-Black (rarely required in interviews)
# When interviews say 'use a BST':
# - LeetCode: implement TreeNode-based solution
# - Real interview: mention sortedcontainers or Java TreeMap equivalent
# - O(log n) operations matter when you need ordered access
# For pure insert/lookup without ordering: use dict (O(1) average)
print('Use heap for priority, dict for lookup, BST for ordered range')Insert Into BST: Edge Cases
Always verify your insert handles: empty tree (return new node as root), duplicate values (define whether to ignore, insert left, or insert right — be consistent), and very large or small values. In interviews, state your assumption about duplicates before coding. The most common convention in LeetCode problems is that all values are distinct unless stated otherwise.
def insert_bst_no_duplicates(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst_no_duplicates(root.left, val)
elif val > root.val:
root.right = insert_bst_no_duplicates(root.right, val)
# else: val == root.val -> duplicate, skip
return root
# Test all edge cases:
root = None
root = insert_bst_no_duplicates(root, 5) # empty tree
root = insert_bst_no_duplicates(root, 5) # duplicate
root = insert_bst_no_duplicates(root, 3)
root = insert_bst_no_duplicates(root, 7)
print(root.val, root.left.val, root.right.val) # 5 3 7BST from Sorted Array
Building a height-balanced BST from a sorted array (LeetCode #108) uses divide-and-conquer: the middle element becomes the root, the left half becomes the left subtree, and the right half becomes the right subtree. This guarantees a balanced tree with height O(log n). The time complexity is O(n) since each element is processed once.
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
nums = [-10, -3, 0, 5, 9]
root = sorted_array_to_bst(nums)
print(root.val) # 0 (middle element)
print(root.left.val) # -3
print(root.right.val) # 9Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: BST property (left subtree strictly less, right subtree strictly greater), search and insert both recursively and iteratively in O(h) time, and worst-case skewed trees where height equals n. Next up we tackle BST deletion and its three cases.
Frequently asked questions
Is the “BST Insert and Search” lesson free?
Yes — the full text of “BST Insert and Search” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “BST Insert and Search”?
Implement recursive and iterative insert and search, trace the path through the tree for various keys, and analyse worst-case complexity for unbalanced trees. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “BST Insert and Search” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.