Pattern 17 of 27

Binary Search Tree Problems

Use the ordering rule of a binary search tree, smaller on the left and larger on the right, to search, validate and edit it without visiting every node.

Cost: O(h) for search and edits, O(n) for full traversals
Problems: 6

When to reach for it

The input is a binary search tree, not just any binary tree.
The prompt mentions the kth smallest value, validation, or finding a value.
An inorder traversal of the tree would come out sorted.

How it works

Every BST question leans on one invariant: all values in the left subtree are smaller than the node and all values in the right subtree are larger. That lets a search discard half the tree at each step, and it makes an inorder traversal emit the values in sorted order, which answers kth smallest and exposes nodes that were swapped. Validation must carry lower and upper bounds down the tree, because comparing a node only with its own children misses violations further down.

The template

Written for Validate Binary Search Tree (write-up)

def is_valid_bst(root, low=float("-inf"), high=float("inf")):
    if not root:
        return True
    if not low < root.val < high:
        return False
    return (is_valid_bst(root.left, low, root.val)
            and is_valid_bst(root.right, root.val, high))

Open in the editor Trace it line by line

Six problems, in learning order

1.Validate Binary Search TreeLeetCode 98Pass lower and upper bounds down the tree, not just the parent's value.Medium
2.Recover Binary Search TreeLeetCode 99An inorder traversal finds the two nodes out of order; swap their values back.Medium
3.Kth Smallest Element in a BSTLeetCode 230Traverse inorder and stop at the kth visit.Medium
4.Lowest Common Ancestor of a Binary Search TreeLeetCode 235Walk down until the two values fall on different sides of the node.Medium
5.Delete Node in a BSTLeetCode 450With two children, copy the successor's value in and delete the successor instead.Medium
6.Search in a Binary Search TreeLeetCode 700Go left or right by comparison; no full traversal needed.Not in the curated 370 yet.Easy

What usually goes wrong

Validating by comparing each node with its children only, which accepts invalid trees.
Ignoring the duplicate-value rule the prompt specifies.
Deleting a node with two children without replacing it by its inorder successor or predecessor.

Binary Search Tree Problems, answered

When should I use the binary search tree problems pattern?

The input is a binary search tree, not just any binary tree. The prompt mentions the kth smallest value, validation, or finding a value. An inorder traversal of the tree would come out sorted.

What is the time complexity of binary search tree problems?

O(h) for search and edits, O(n) for full traversals. Validation must carry lower and upper bounds down the tree, because comparing a node only with its own children misses violations further down.

Which problem should I start with for binary search tree problems?

Start with Validate Binary Search Tree (LeetCode 98, Medium). Pass lower and upper bounds down the tree, not just the parent's value. The six problems on this page are in learning order.