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.
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 found