Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtree-dfs

Validate Binary Search Tree

Problem (restated)

Determine whether a binary tree is a valid BST: every node is strictly greater than all in its left subtree and strictly less than all in its right.

Intuition

Pass (low, high) down each edge. Node value must lie inside the open interval.

Approaches

Bounds DFS

Tested only

Time O(n)Space O(h)

Idea. isValid(node, low, high): null ok; low < val < high; recurse left (low,val) and right (val,high).

Walkthrough. Invalid classic: root 5, right 4 (4 is not > 5).

Trade-offs. Bounds DFS is clean; inorder must be strictly increasing.

Solution

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

export function isValidBST(root: TreeNode | null): boolean {
  const go = (node: TreeNode | null, low: number, high: number): boolean => {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return go(node.left, low, node.val) && go(node.right, node.val, high);
  };
  return go(root, -Infinity, Infinity);
}

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

export function isValidBST(root: TreeNode | null): boolean {
  const go = (node: TreeNode | null, low: number, high: number): boolean => {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return go(node.left, low, node.val) && go(node.right, node.val, high);
  };
  return go(root, -Infinity, Infinity);
}

Template connection

Tree DFS with state passed down.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?