DSA sheet · Binary Search Tree · DFS pattern

Validate BST

Given any binary tree, decide whether it is a real binary search tree. It sounds easy, but it has a famous trap: checking each node only against its own children is not enough. The teacher first solves it "from below" (for each node, go down and fetch the biggest value on its left and the smallest value on its right), which costs O(n log n) or worse. Then she flips the idea and checks "from above": every node gets an allowed range (min limit, max limit) passed down from its ancestors. That brings it down to O(n).

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (and the parent-child trap)
• Part A · Brute force: max of left, min of right, at every node
• Part B · Optimal: pass a (min, max) range down
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

Each node holds a value, a left link and a right link. A missing child is None.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The BST rule, said carefully

A tree is a valid BST when, for every node:

• every value in its left subtree (the left child and everything under it) is strictly smaller than the node,
• every value in its right subtree (the right child and everything under it) is strictly bigger than the node,
• and the left and right subtrees are themselves valid BSTs.

Short form: left subtree < node < right subtree, at every node. "Strictly" means equal values are not allowed: a duplicate makes the tree invalid.

Another way to say the same rule, which the teacher uses: a node must be bigger than the maximum of its left subtree and smaller than the minimum of its right subtree. If it beats the biggest value on the left, it beats all of them.

The trap: checking only parent and child is not enough

A tempting shortcut is "for each node, check left.val < node.val < right.val". That only compares a node with its direct children. It misses values deeper down that are on the wrong side of an ancestor.

      5
     / \
    1   6
       / \
      3   7

        5
      /   \
     3     7
      \   / \
       4 6   8
            /
           2

Small example: every parent-child pair looks fine. 1 < 5 < 6 ✓. 3 < 6 < 7 ✓. But 3 is in the right subtree of 5, so it must be bigger than 5, and it isn't. Not a BST.

Teacher's tree: 3 < 5 ✓, 7 > 5 ✓, 4 > 3 ✓, 6 < 7 ✓, 8 > 7 ✓, 2 < 8 ✓. Every pair passes. Yet the circled 2 sits under 8 (fine), which is under 7 (so it must be > 7), which is under 5 (so it must be > 5). 2 breaks both. Not a BST.

So a node's limits come from all its ancestors, not just its parent. Both parts below are built around this.

Inorder of a BST is sorted (useful fact)

Inorder traversal means: visit the left subtree, then the node, then the right subtree. In a BST, everything visited before a node (its left side) is smaller and everything after it (its right side) is bigger, and this holds at every level. So the inorder list of a valid BST is strictly increasing. For the small counter-example the inorder list is 1 5 3 6 7, which is not sorted. That's another sign it's not a BST. (The teacher doesn't use this method in the video; it's mentioned in the revision page as a check.)

Part A · Brute force: max of left, min of right, at every node

LeetCode 98 · Validate Binary Search Tree

1The question in simple words

You get the root of a binary tree. Return True if it is a valid BST (the rule in Part 0 holds at every node), otherwise False.

        5
      /   \
     3     7
      \   /
       4 6

        5
      /   \
     3     7
      \   / \
       6 6   8

2What the constraints tell us

• Number of nodes: 1 to 10⁴. At least one node, so the root exists. We still need a None base case inside the recursion, because the children can be None.
• 10⁴ nodes: O(n²) = 10⁸ is right at the edge of TLE. We should aim for linear, O(n).
• Values: −2³¹ to 2³¹ − 1. These are the very edges of a 32-bit int. We only compare values, never add or multiply them, so comparing is safe. But this range matters later when we pick the starting limits (Part B, Doubt 4).

3Intuition: ask each node to look down

Stand at a node. Ask: "what's the biggest value in my left subtree, and the smallest value in my right subtree?" If the node is bigger than the first and smaller than the second, this node is fine. Then do the same at every other node. One failing node is enough to say the whole tree is not a BST.

4Building the conditions from examples

How to fetch the maximum of the left subtree cheaply

The teacher's trick: the biggest value in a BST is at the end of the rightmost path, so from the left child, keep stepping right until there's no right child. Likewise the smallest value of the right subtree is found by starting at the right child and stepping left all the way. Going the other direction makes no sense: stepping left only finds smaller values, which can't be the maximum.

Example 1 (3's right child is 6)

        5
      /   \
     3     7
      \   / \
       6 6   8
            /
           2

At 5: walk right from 3 → 6. So the max of the left side is 6. Is 5 > 6? No. We know straight away it's not a BST, at the very first node.

Example 2 (change 3's right child to 2)

At 5: walk right from 3 → 2, so the left max is 2. 5 > 2 ✓. Walk left from 7 → 6, so the right min is 6. 5 < 6 ✓. Node 5 is fine.

Next, at 3: the left child is None, so there's nothing on the left to beat. The right side: walk left from 2 → 2, so the min is 2. Is 3 < 2? No → return False right there. A single bad node makes the whole tree invalid.

5Approach steps

1. If the node is None → return True.
2. If it has a left child: walk right from the left child to the end. If that value is ≥ the node → return False.
3. If it has a right child: walk left from the right child to the end. If that value is ≤ the node → return False.
4. Return (left subtree is valid) and (right subtree is valid).

6Code (Python)

class Solution:
    def isValidBST(self, root):
        if root is None:
            return True
        if root.left is not None:              # max of the left subtree
            node = root.left
            while node.right is not None:
                node = node.right
            if node.val >= root.val:
                return False
        if root.right is not None:             # min of the right subtree
            node = root.right
            while node.left is not None:
                node = node.left
            if node.val <= root.val:
                return False
        return self.isValidBST(root.left) and self.isValidBST(root.right)

7Code line by line

8Dry run (Example 2)

1. f(5): left max = 2 (3 → 2), 2 < 5 ✓. Right min = 6 (7 → 6), 6 > 5 ✓. Now check the left subtree. f(5) waits.
2. f(3): no left child, skip. Right min = 2 (just the node 2). Is 2 > 3? No → False.
3. f(5) gets False from the left. With and, Python doesn't even run the right side. Final answer: False ✓

9Complexity & remember

• Time: at each of the n nodes we do two walks, each up to the height h. That's O(n · h).
  • Balanced tree: h ≈ log n, so about n · 2 log n → O(n log n).
  • Skewed tree (a straight line): h ≈ n → O(n²). With n = 10⁴ that's 10⁸, which is risky.
• Space O(h) for the recursion stack.

Can we do better? The teacher's reasoning: to be sure a tree is valid we have to look at every node at least once, so O(n) is the best possible. The waste in this version is that every node walks down again and again over the same nodes.

Part B · Optimal: pass a (min, max) range down

Same question and constraints as Part A. The new idea changes the direction of the check.

1Intuition: check from above, not from below

In Part A, every node looked down to see what was beneath it. Now we flip it: as we go down, the ancestors tell each child "you're allowed to be anything between these two limits".

• The root can be anything: its range is (−∞, +∞).
• Going to the root's left child (3): it can be anything, as long as it's less than 5. So its range is (−∞, 5). The node's own value becomes the new max limit.
• Going to the root's right child (7): anything, as long as it's more than 5. Range (5, +∞). The node's value becomes the new min limit.

Every node must sit strictly inside its range. If one doesn't → False.

2What changes from Part A

No more walks down the tree. Each node does one constant-time check against two numbers it received from above. The limits carry the information from all the ancestors, which is exactly what the parent-child shortcut was missing.

3Building the conditions from examples

The function shape

A helper check(node, low, high): "is this subtree a valid BST, if every value in it must be strictly between low and high?" Start with check(root, −∞, +∞).

When to say False

The node is out of range if it's at or below the min limit, or at or above the max limit:

When the node is None

Going down: which limit changes?

• Left child: low stays the same, high becomes node.val → check(node.left, low, node.val).
• Right child: low becomes node.val, high stays the same → check(node.right, node.val, high).

Combining: AND, not OR

Suppose the left side says True and the right side says False. Is the tree valid? No, because one bad node anywhere spoils it. With or, True or False = True, which would be wrong. So we join the two calls with and. A bonus: if the left side is already False, Python skips the right call.

4Approach steps

1. Call check(root, −∞, +∞).
2. If the node is None → True.
3. If val <= low or val >= high → False.
4. Return check(left, low, val) and check(right, val, high).

5Code (Python)

class Solution:
    def isValidBST(self, root):
        return self.check(root, float('-inf'), float('inf'))

    def check(self, node, low, high):
        if node is None:
            return True
        if node.val <= low or node.val >= high:     # outside the allowed range
            return False
        return (self.check(node.left, low, node.val) and     # left: new max
                self.check(node.right, node.val, high))      # right: new min

6Code line by line

7Dry run

Run 1: the tree where 3's right child is 2.

        5
      /   \
     3     7
      \   / \
       2 6   8

1. check(5, −∞, +∞): inside ✓ → go left with (−∞, 5).
2. check(3, −∞, 5): inside ✓ → go left with (−∞, 3).
3. check(None) → True. Back in 3, go right with (3, 5). The max 5 is inherited from the parent, not +∞.
4. check(2, 3, 5): 2 ≤ 3 → False.
5. 3 gets True and False → False. 5's left is False, so and skips the right side. Final answer: False ✓

Run 2: change that 2 to 4, and 8 has a left child 2 (the teacher's second check).

        5
      /   \
     3     7
      \   / \
       4 6   8
            /
           2

8's left is False, so 8 returns False without checking its right. 7 gets True and False → False. 5 gets True and False → False. Final answer: False ✓. The bad node was found only near the bottom, which is the worst case: we may visit almost every node before finding it.

8Complexity

• Time O(n): each node is visited once and does one constant-time check. The teacher's point: we went from O(n log n) / O(n²) down to O(n) because we check from above instead of walking down from every node.
• Space O(h) for the call stack: O(log n) for a balanced tree, O(n) for a skewed one. The teacher simply says O(n), which is the worst case.

9Remember

Part C · Revision page

good  = TreeNode(5, TreeNode(3, None, TreeNode(4)), TreeNode(7, TreeNode(6), TreeNode(8)))
bad1  = TreeNode(5, TreeNode(3, None, TreeNode(2)), TreeNode(7, TreeNode(6), TreeNode(8)))
bad2  = TreeNode(5, TreeNode(3, None, TreeNode(4)),
                 TreeNode(7, TreeNode(6), TreeNode(8, TreeNode(2))))
trap  = TreeNode(5, TreeNode(1), TreeNode(6, TreeNode(3), TreeNode(7)))
dup   = TreeNode(2, TreeNode(2), TreeNode(2))
edge  = TreeNode(2**31 - 1)

s = Solution()
print(s.isValidBST(good))   # True
print(s.isValidBST(bad1))   # False
print(s.isValidBST(bad2))   # False
print(s.isValidBST(trap))   # False  (parent-child check would say True)
print(s.isValidBST(dup))    # False
print(s.isValidBST(edge))   # True

Based on this video: Validate Binary Search Tree