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

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

• Checking the parent is not enough. A value deep on the right can still be smaller than the root. The open range (low, high) is what travels down.
• An equal child is not a BST. For a value at the integer limit, leave the bound null. Do not use MinValue as if it were a real limit.
• One node is true. An empty tree is true.