Validate Binary Search Tree

This blog series attempts to solve the 500 Top Leet Code Interview Questions with the help of AI Code Assistance, such as Gemini and GPT.

Question 108:

Validate Binary Search Tree

Given the root of a binary tree, we need to determine if it is a valid Binary Search Tree (BST).

A BST follows these rules:

1. The left subtree of a node contains only nodes with values less than the node’s value.
2. The right subtree of a node contains only nodes with values greater than the node’s value.
3. Both left and right subtrees must also be BSTs.

Examples Explained

Example 1

Input: root = [2,1,3]
Tree Structure:

    2
   / \
  1   3

• 1 < 2 (valid left subtree)
• 3 > 2 (valid right subtree)
• No violations → Valid BST Output: true

Example 2

Input: root = [5,1,4,null,null,3,6]
Tree Structure:

    5
   / \
  1   4
     / \
    3   6

• 1 < 5 (valid left subtree)
• 4 < 5 (seems valid, but...)
• 3 < 4 (valid), 6 > 4 (valid)
• Issue: 3 is in the right subtree of 5, but 3 < 5, which violates the BST…