Solving Validate Binary Search Tree: Ensuring Proper Order

The "Validate Binary Search Tree" problem involves checking whether a binary tree meets the criteria of a binary search tree (BST). In a BST, the left subtree of a node contains only nodes with keys lesser than the node's key, and the right subtree only nodes with keys greater.

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

Example

Consider a binary tree:

This tree is a valid BST.

Solution Approach - Recursive Traversal

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

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

function isValidBST(root: TreeNode | null): boolean {
  return validate(root, null, null);

  function validate(node: TreeNode | null, low: number | null, high: number | null): boolean {
    if (node === null) return true;
    if ((low !== null && node.val <= low) || (high !== null && node.val >= high)) return false;
    return validate(node.left, low, node.val) && validate(node.right, node.val, high);
  }
}

Breaking Down the Solution

• Recursive Strategy: The function validate recursively checks each node.
• Boundary Conditions: Each node's value is compared against the allowed range (low and high) determined by its ancestors.
• Left and Right Subtree Checks: Ensures that left child values are less than the node's value and right child values are greater.

Conclusion

Validating a binary search tree is a fundamental problem in tree algorithms, highlighting the importance of recursion and boundary conditions in tree traversal.