Understanding BST Properties: Implementation Guide

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Each TreeNode holds its value and two optional children. A leaf node simply has None for both children.

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Python — Recursive Inorder

def inorder(root):
    result = []
    def traverse(node):
        if not node:
            return
        traverse(node.left)       # Visit left subtree first
        result.append(node.val)   # Then current node
        traverse(node.right)      # Then right subtree
    traverse(root)
    return result

Time: O(n) — visits every node once. Space: O(h) for the call stack, where h is the tree height (O(log n) balanced, O(n) worst case).

Python — Iterative Kth Smallest

def kth_smallest(root, k):
    stack = []
    node = root
    count = 0

    while stack or node:
        while node:
            stack.append(node)    # Push all left descendants
            node = node.left
        node = stack.pop()        # Process the smallest unvisited
        count += 1
        if count == k:            # Found the kth element
            return node.val
        node = node.right         # Move to right subtree

    return None  # k is out of bounds

The inner while node loop pushes the leftmost path onto the stack. Then we pop the smallest, count it, and if it matches k, we return immediately. This avoids visiting the entire tree.

Time: O(k) in the best case (stops early). Space: O(h) for the stack.

Java — Iterative Kth Smallest

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    int count = 0;

    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        count++;
        if (count == k) return node.val;
        node = node.right;
    }
    throw new IllegalArgumentException("k out of bounds");
}

C++ — Iterative Kth Smallest

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> stk;
    TreeNode* node = root;
    int count = 0;

    while (!stk.empty() || node != nullptr) {
        while (node != nullptr) {
            stk.push(node);
            node = node->left;
        }
        node = stk.top(); stk.pop();
        count++;
        if (count == k) return node->val;
        node = node->right;
    }
    return -1;
}

class AugNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.size = 1  # Includes this node

def update_size(node):
    if node:
        left_size = node.left.size if node.left else 0
        right_size = node.right.size if node.right else 0
        node.size = 1 + left_size + right_size

Now, at each node, if left_size + 1 == k, the current node is the answer. If k is smaller, go left. If k is larger, go right with k -= (left_size + 1). This gives O(log n) per query on a balanced tree.

Search

def search(root, target):
    node = root
    while node:
        if target == node.val:
            return node
        elif target < node.val:
            node = node.left
        else:
            node = node.right
    return None

Start at root. Go left if target is smaller, right if larger. Repeat until found or null is reached.

Insert

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

Navigate to the correct leaf position and create the node. Returns the (possibly new) root.

Find Minimum and Maximum

def find_min(root):
    if not root: return None
    while root.left:
        root = root.left
    return root.val

def find_max(root):
    if not root: return None
    while root.right:
        root = root.right
    return root.val

Minimum is always the leftmost node. Maximum is always the rightmost node.

def delete(root, val):
    if not root:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        successor = find_min_node(root.right)
        root.val = successor.val
        root.right = delete(root.right, successor.val)
    return root

Off-by-One in K

Remember that k is 1-indexed: k=1 means the smallest element, k=2 means the second smallest. If you use a 0-indexed counter internally, adjust accordingly: return when count == k if your counter starts at 0 and increments before checking.

Handling Unbalanced Trees

If elements are inserted in sorted or nearly sorted order, the BST degrades to a linked list. All operations drop to O(n). In production, use self-balancing BSTs (AVL, Red-Black) or shuffle input before insertion when possible.

Integer Overflow

In Java and C++, be cautious with integer operations on node values during subtree size calculations or comparisons. Use long in Java or long long in C++ if there is any risk of overflow.