​
Core Implementation

​
Basic Binary Search Tree

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # For AVL tree usage
        
class BST:
    def __init__(self):
        self.root = None
        
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        self._insert_recursive(self.root, val)
    
    def _insert_recursive(self, node, val):
        if not node:
            return TreeNode(val)
        
        if val < node.val:
            node.left = self._insert_recursive(node.left, val)
        else:
            node.right = self._insert_recursive(node.right, val)
        return node
    
    def search(self, val):
        return self._search_recursive(self.root, val)
    
    def _search_recursive(self, node, val):
        if not node or node.val == val:
            return node
            
        if val < node.val:
            return self._search_recursive(node.left, val)
        return self._search_recursive(node.right, val)
    
    def delete(self, val):
        self.root = self._delete_recursive(self.root, val)
    
    def _delete_recursive(self, node, val):
        if not node:
            return None
            
        if val < node.val:
            node.left = self._delete_recursive(node.left, val)
        elif val > node.val:
            node.right = self._delete_recursive(node.right, val)
        else:
            # Node with one or no child
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
                
            # Node with two children
            successor = self._find_min(node.right)
            node.val = successor.val
            node.right = self._delete_recursive(node.right, successor.val)
        
        return node
    
    def _find_min(self, node):
        current = node
        while current.left:
            current = current.left
        return current

​
Implementation Variations

​
1. AVL Tree (Self-balancing BST)

class AVLTree(BST):
    def insert(self, val):
        self.root = self._insert_recursive(self.root, val)
    
    def _insert_recursive(self, node, val):
        # Normal BST insert
        if not node:
            return TreeNode(val)
        
        if val < node.val:
            node.left = self._insert_recursive(node.left, val)
        else:
            node.right = self._insert_recursive(node.right, val)
            
        # Update height
        node.height = 1 + max(self._get_height(node.left),
                             self._get_height(node.right))
        
        # Get balance factor
        balance = self._get_balance(node)
        
        # Balance the tree
        # Left Left Case
        if balance > 1 and val < node.left.val:
            return self._rotate_right(node)
            
        # Right Right Case
        if balance < -1 and val > node.right.val:
            return self._rotate_left(node)
            
        # Left Right Case
        if balance > 1 and val > node.left.val:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
            
        # Right Left Case
        if balance < -1 and val < node.right.val:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)
            
        return node

​
2. Threaded Binary Search Tree

class ThreadedNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.is_threaded = False

class ThreadedBST:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        if not self.root:
            self.root = ThreadedNode(val)
            return
            
        current = self.root
        while current:
            if val < current.val:
                if not current.left:
                    current.left = ThreadedNode(val)
                    current.left.right = current
                    current.left.is_threaded = True
                    break
                current = current.left
            else:
                if not current.right or current.is_threaded:
                    old_right = current.right
                    current.right = ThreadedNode(val)
                    current.right.right = old_right
                    current.right.is_threaded = True
                    current.is_threaded = False
                    break
                current = current.right

​
Time Complexities

OperationBST (Average)BST (Worst)AVL TreeThreaded BST
InsertO(log n)O(n)O(log n)O(log n)
DeleteO(log n)O(n)O(log n)O(log n)
SearchO(log n)O(n)O(log n)O(log n)
Min/MaxO(log n)O(n)O(log n)O(1)*
SuccessorO(log n)O(n)O(log n)O(1)
PredecessorO(log n)O(n)O(log n)O(1)
TraversalO(n)O(n)O(n)O(n)
* With additional pointers to min/max

​
Space Complexities

ImplementationSpace ComplexityAdditional Notes
Basic BSTO(n)No additional overhead
AVL TreeO(n)Extra space for height information
Threaded BSTO(n)Extra space for thread indicators
Balanced BSTO(n)May need temp space during rebalancing

​
Common Data Structure Patterns

  1. Tree Traversal Patterns
    • Inorder (sorted order)
    • Preorder (copying tree)
    • Postorder (deletion)
    • Level-order (breadth-first)
  2. Range Query Patterns
    • Find elements in range
    • Count elements in range
    • Find closest element
  3. Balancing Patterns
    • Single rotations
    • Double rotations
    • Height balancing
  4. Predecessor/Successor
    • Next greater element
    • Previous smaller element
    • Inorder traversal
  5. Path Patterns
    • Root to leaf paths
    • Lowest common ancestor
    • Path sum problems
  6. Modification Patterns
    • BST to greater sum tree
    • Merge BSTs
    • Split BST

​
Edge Cases to Consider

  1. Empty Tree
if not self.root:
    return None
  1. Single Node
if not root.left and not root.right:
    return root.val
  1. Duplicate Values
# Option 1: Maintain count
class NodeWithCount(TreeNode):
    def __init__(self, val):
        super().__init__(val)
        self.count = 1

# Option 2: Use left/right convention
if val <= node.val:  # Allow duplicates to left
    node.left = self._insert_recursive(node.left, val)
  1. Unbalanced Input
# Handle sorted input causing linear tree
def insert_balanced(self, sorted_vals):
    if not sorted_vals:
        return None
    mid = len(sorted_vals) // 2
    root = TreeNode(sorted_vals[mid])
    root.left = self.insert_balanced(sorted_vals[:mid])
    root.right = self.insert_balanced(sorted_vals[mid + 1:])
    return root

​
Optimization Techniques

  1. Caching Height/Size
class OptimizedNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1
        self.size = 1
        self.sum = val  # Subtree sum
  1. Parent Pointers
class NodeWithParent:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
  1. Bulk Operations
def build_from_sorted_array(self, arr):
    def build(start, end):
        if start > end:
            return None
        mid = (start + end) // 2
        node = TreeNode(arr[mid])
        node.left = build(start, mid - 1)
        node.right = build(mid + 1, end)
        return node
    
    self.root = build(0, len(arr) - 1)

​
Memory Management

  1. Node Pooling
class NodePool:
    def __init__(self, size=1000):
        self.pool = [TreeNode(0) for _ in range(size)]
        self.available = list(range(size))
    
    def get_node(self, val):
        if not self.available:
            return TreeNode(val)
        idx = self.available.pop()
        node = self.pool[idx]
        node.val = val
        node.left = node.right = None
        return node

    def return_node(self, node):
        if len(self.available) < len(self.pool):
            self.available.append(node)
  1. Tree Cleanup
def clear_tree(self):
    def recursive_clear(node):
        if not node:
            return
        recursive_clear(node.left)
        recursive_clear(node.right)
        node.left = node.right = None
        node.val = None
    
    recursive_clear(self.root)
    self.root = None

​
Performance Considerations

  1. Iterative vs Recursive
def search_iterative(self, val):
    current = self.root
    while current:
        if current.val == val:
            return current
        current = current.left if val < current.val else current.right
    return None
  1. Batch Processing
def process_range(self, start, end, batch_size=1000):
    result = []
    current = self.find_ceiling(start)
    
    while current and current.val <= end:
        result.append(current.val)
        if len(result) == batch_size:
            process_batch(result)
            result = []
        current = self.successor(current)

​
Common Pitfalls

  1. Incorrect Balance Handling
# Wrong
def is_balanced(self, root):
    if not root:
        return True
    return abs(height(root.left) - height(root.right)) <= 1

# Correct
def is_balanced(self, root):
    if not root:
        return True
    left_height = self._get_height(root.left)
    right_height = self._get_height(root.right)
    return (abs(left_height - right_height) <= 1 and
            self.is_balanced(root.left) and
            self.is_balanced(root.right))
  1. Memory Leaks in Deletion
# Wrong
def delete(self, node):
    if node.right:
        node.val = successor.val
        node.right = None  # Memory leak

# Correct
def delete(self, node):
    if node.right:
        successor = self._find_min(node.right)
        node.val = successor.val
        node.right = self._delete_recursive(node.right, successor.val)
  1. Incorrect BST Property Validation
# Wrong: Doesn't check subtrees properly
def is_bst(self, root):
    if not root:
        return True
    if root.left and root.left.val > root.val:
        return False
    if root.right and root.right.val < root.val:
        return False
    return True

# Correct
def is_bst(self, root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (self.is_bst(root.left, min_val, root.val) and
            self.is_bst(root.right, root.val, max_val))