Pattern visualizer
Largest BST in Binary Tree
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. 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)..
Bottom-up postorder synthesis (isBST, size, min, max)
time O(n)space O(h) recursion stackstep 1 / 13
1
5
8
10
15
7
Call stack
largest(10)
line 1
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 + 17 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