🌲 Blog 9: Binary Search Tree (BST) Patterns

[Dev Cookies]

Why This Pattern?​

A Binary Search Tree (BST) isn’t just a binary tree —
it comes with ordering constraints:

• Left subtree < Node < Right subtree.
• Inorder traversal = sorted sequence.

Many problems become much easier once you recognize “BST property can be leveraged”.

🛠 Core Idea (Template)​

• Use inorder traversal to exploit sorted order.
• Use binary search property to prune unnecessary paths.
• Use range constraints when validating or searching.

Classic Problems​

1. Validate BST (LeetCode 98)​

Check if tree satisfies BST property.

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValid(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }
}

Pattern: DFS with range constraints.

2. Lowest Common Ancestor in BST (LeetCode 235)​

Find LCA efficiently using BST property.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                return root; // Split point
            }
        }
        return null;
    }
}

Pattern: BST-guided search (pruning).

3. Kth Smallest Element in BST (LeetCode 230)​

Inorder = sorted → kth element.

class Solution {
    int count = 0, result = -1;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null) return;
        inorder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inorder(node.right, k);
    }
}

Pattern: Inorder traversal → sorted order.

4. Convert Sorted Array to BST (LeetCode 108)​

Classic construction problem.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int mid = (l + r) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, l, mid - 1);
        root.right = build(nums, mid + 1, r);
        return root;
    }
}

Pattern: Divide & Conquer using BST structure.

5. Inorder Successor in BST (LeetCode 285)​

Find the smallest node > target.

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while (root != null) {
            if (p.val < root.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return successor;
    }
}

Pattern: BST search + candidate tracking.

6. Range Sum of BST (LeetCode 938)​

Sum of values within [low, high].

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val < low) return rangeSumBST(root.right, low, high);
        if (root.val > high) return rangeSumBST(root.left, low, high);
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}

Pattern: Prune branches outside range.

Advanced Problems​

1. Serialize & Deserialize BST (LeetCode 449) – exploit preorder with BST constraints.
2. Balance BST (LeetCode 1382) – inorder → sorted array → rebuild.
3. Closest Value in BST (LeetCode 270) – search path, keep closest.
4. Two Sum in BST (LeetCode 653) – inorder (sorted array) + 2-pointer.

Quick Pattern Checklist​

• Inorder = sorted → Kth element, 2-sum, median.
• BST property → prune search (range queries, LCA).
• Construction → sorted array/list → balanced BST.
• Successor/Predecessor → candidate tracking in search.

Key Takeaway:
BST problems are usually simplified to:

• Traversal (sorted)
• Search (guided by property)
• Range/Order queries (pruning)

Continue reading...

 

Join 𝕋𝕄𝕋 on Telegram
Channel PREVIEW: