p16 — Hints

Open one at a time. Spend at least 90 seconds re-attempting between hints.

Hint 1 — Diagnostic

Did you write node.left.val < node.val < node.right.val? Trace your code on [5,1,4,null,null,3,6]. Draw the tree. Notice the 3 sitting in the right subtree of 5. What constraint does 5 impose on 3 that your code never checks?

Hint 2 — The Invariant

Re-state the BST property out loud, precisely:

For every node, ALL values in its left subtree are strictly less than node.val, AND ALL values in its right subtree are strictly greater.

Note “ALL” — not just immediate children. Your code must enforce this for descendants arbitrarily deep.

Hint 3 — Two Templates

There are two clean ways to enforce the all-descendants invariant:

  1. Pass bounds down. Each recursive call carries (lo, hi) — the open interval the subtree’s values must lie in. Initially (None, None) = unbounded. When recursing left, tighten hi = node.val. When recursing right, tighten lo = node.val.
  2. Walk inorder, check monotone. Inorder of a valid BST is a strictly increasing sequence. Walk inorder, remember the previous value, and reject if any successor isn’t strictly greater.

Pick one and code it. (For the second pass, code the other.)

Hint 4 — Pseudocode (Bounds)

def go(node, lo, hi):
    if node is None: return True
    if lo is not None and node.val <= lo: return False
    if hi is not None and node.val >= hi: return False
    return go(node.left, lo, node.val) and go(node.right, node.val, hi)

Three things to double-check:

  • Use <= / >= to enforce strict BST.
  • Tighten hi when going left, lo when going right (not the other way).
  • Sentinels: None means “no bound on that side.” Don’t use float('inf') if you want this to port to Java cleanly.

Hint 5 — Pseudocode (Iterative Inorder)

stack, cur, prev = [], root, None
while cur or stack:
    while cur:
        stack.append(cur)
        cur = cur.left
    node = stack.pop()
    if prev is not None and node.val <= prev:
        return False
    prev = node.val
    cur = node.right
return True

This is the form to memorize — it appears verbatim in p18 (Kth Smallest), LC 173 (BST Iterator), and LC 285 (Inorder Successor). Practice writing it without looking until you can do it in 90 seconds.