Skip to content

Topic 10 of 20

Binary Search Trees

Use the ordering invariant: inorder is sorted, and every step discards a subtree.

15 problems5 Easy8 Medium2 Hard

The concept

A binary search tree keeps every value in a node's left subtree smaller than the node and every value in the right subtree larger. That single invariant gives you two superpowers. You can search, insert and delete in O(h) time by going left or right at each step. And an inorder traversal visits the values in sorted order.

Most BST interview questions are really asking you to exploit one of those properties. Validating a BST means passing down the allowed (min, max) range. Finding the k-th smallest means stopping an inorder traversal early. Converting a sorted array into a balanced BST means always choosing the middle element as the root.

Remember that h is O(log n) only for balanced trees and O(n) in the worst case. Production code uses self-balancing trees (red-black, AVL) exposed as ordered sets and maps, such as TreeMap in Java or std::set in C++. The last problems here use them to answer "nearest value" queries efficiently.

Patterns you will learn

Problems, in order

  1. 1

    Walk left or right; the O(h) search every BST operation builds on.

    BST SearchReported at: Amazon
  2. 2

    Skipping subtrees that fall outside the range.

    BST PruningReported at: MetaAmazonApple
  3. 3

    Choosing the middle element produces a balanced BST.

    Divide & ConquerReported at: AmazonMetaApple+2
  4. 4

    Adjacent inorder values give the minimum difference.

    Inorder = SortedReported at: Google
  5. 5

    Two Sum on a tree, via a sorted inorder list or a hash set.

    Inorder + Two Pointers / Hash SetReported at: AmazonUber
  6. 6

    Passing (min, max) bounds down; one of the most-asked tree problems.

    BST Invariant (Bounds)Reported at: AmazonMetaMicrosoft+5
  7. 7

    Early-stopping inorder traversal.

    Inorder = SortedReported at: AmazonMetaMicrosoft+2
  8. 8

    LCA becomes a simple walk thanks to ordering.

    BST InvariantReported at: MetaAmazonApple+3
  9. 9

    Recursive insertion that preserves the invariant.

    BST Insert / DeleteReported at: AmazonLinkedInGoldman Sachs
  10. 10

    Deletion with the inorder successor; tests case analysis.

    BST Insert / DeleteReported at: AmazonMicrosoftGoogle+2
  11. 11

    Lazy inorder with a stack in O(h) memory.

    Controlled Inorder (Stack)Reported at: MetaMicrosoftAmazon+3
  12. 12

    Bounds-based construction in O(n).

    BST Invariant (Bounds)Reported at: AmazonMicrosoftMeta+1
  13. 13

    Finding two swapped nodes via inorder anomalies.

    Inorder = SortedReported at: AmazonMicrosoftApple+3
  14. 14

    Ordered-set or bucket window for nearby-value queries.

    Ordered Set / BucketsReported at: GoogleAmazonApple+1
  15. 15

    Return BST validity, bounds and sum from each subtree.