DSA Tracker

Visualize

Largest BST Subtree

Bottom-up postorder synthesis (isBST, size, min, max)

time O(n)space O(h) recursion stack

Checking every subtree from the top down re-validates the same nodes over and over. Working bottom-up (postorder) fixes that: solve both children first, then decide the parent using only their answers. Each call returns whether its subtree is a BST, its size, and its min/max values — a parent combines its children's results in O(1) instead of re-scanning them.

Details

Animated on: root = [10, 5, 15, 1, 8, null, 7] — find the size of the largest subtree that is a valid BST. Expected answer: 3 (the subtree rooted at 5, containing 1, 5, 8).

Problem:Largest BST SubtreeHard

Bottom-up postorder synthesis (isBST, size, min, max)

step 1 / 13

1
5
8
10
15
7

Call stack

largest(10)

Enter 10. Its subtrees must be solved first (postorder) before 10 can be judged.

Pseudocode
1FUNCTION largest(node):
2  IF node = null: RETURN {ok: true, size: 0, lo: +inf, hi: -inf}
3  left <- largest(node.left)
4  right <- largest(node.right)
5  IF left.ok AND right.ok AND left.hi < node.val AND node.val < right.lo:
6    size <- left.size + right.size + 1
7    best <- MAX(best, size)
8    RETURN {ok: true, size, lo: MIN(left.lo, node.val), hi: MAX(right.hi, node.val)}
9  RETURN {ok: false, size: 0, lo: -inf, hi: +inf}
10answer <- best

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. Enter 10. Its subtrees must be solved first (postorder) before 10 can be judged.
  2. Enter 5. Its subtrees must be solved first (postorder) before 5 can be judged.
  3. Enter 1. It is a leaf, so both children are empty subtrees.
  4. 1 is a leaf: empty children are trivially valid, so it is a BST of size 1 by itself. New best BST size is 1.
  5. Enter 8. It is a leaf, so both children are empty subtrees.
  6. 8 is a leaf: empty children are trivially valid, so it is a BST of size 1 by itself. Best stays 1.
  7. Both sides are BSTs and 1 < 5 < 8 holds, so 5 joins them into one BST of size 3. New best BST size is 3.
  8. Enter 15. Its subtrees must be solved first (postorder) before 15 can be judged.
  9. Enter 7. It is a leaf, so both children are empty subtrees.
  10. 7 is a leaf: empty children are trivially valid, so it is a BST of size 1 by itself. Best stays 3.
  11. 15 fails: 15 does not sit strictly between left-max -Infinity and right-min 7. This subtree cannot be a BST.
  12. 10 fails: its right subtree already failed. This subtree cannot be a BST.
  13. Whole tree done. The largest BST found anywhere is size 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Largest BST Subtree in the editorAll BST problemsBack to roadmap