Validate Binary Search Tree

Problem Statement

Determining whether a given binary tree is a valid binary search tree (BST) involves verifying several crucial conditions. A BST must satisfy the following requirements for each node in the tree:

• The nodes in the left subtree must have values strictly less than the node's own value.
• Conversely, the nodes in the right subtree must have values strictly greater than the node's own value.
• Both the left and right subtrees themselves must also adhere to the rules of BSTs.

These criteria ensure that a BST maintains a sorted structure, which allows for efficient search, insert, and delete operations. Validation of these criterias across a dynamic set of conditions and structures defines its utility and correctness.

Examples

Example 1

Input:

root = [2,1,3]

Output:

true

Example 2

Input:

root = [5,1,4,null,null,3,6]

Output:

false

Explanation:

The root node's value is 5 but its right child's value is 4.

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

Approach and Intuition

From the given examples, we can derive a clear understanding of what makes a binary tree a valid BST and what doesn't. Let's use these examples to build our understanding and approach:

1. Example 1:

   • Input: root = [2,1,3]
   • The root node here is 2, with left child 1 and right child 3. This directly satisfies our conditions for a BST:
     • Left child (1) < root node (2)
     • Right child (3) > root node (2)
   • Both the subtrees are further trivially valid as they are just single nodes.

2. Example 2:

   • Input: root = [5,1,4,null,null,3,6]
   • For this tree, the root is 5. The left child is 1 (which is fine), but the right child is 4. Here’s where the problem lies:
     • Although 4 > root (5) condition fails outright, further 4's subtree contains 3 and 6, where 3 is not greater than 5, which violates the BST condition for all descendant nodes of the right subtree.
   • This example fails the BST check because nodes within subtrees must maintain the overall BST properties, not just in relation to their immediate parent.

These examples impart the essence of the approach to validate a BST:

• Check recursively for every node if it satisfies the BST condition with respect to its parent.
• Implement checks using boundaries for allowable values that update as one moves down the tree, ensuring valid subtrees maintain BST properties relative to all ancestor nodes, not just their parents. This approach typically involves the use of helper functions or iterative solutions leveraging stacks.

Given the constraints, the validation process can be efficiently managed within the limits using recursive depth-first approaches or iterative methods, whichever suits the specific scenarios or personal preferences.

Solutions

class Solution {
public:
    bool isBinarySearchTree(TreeNode* node) {
        stack<TreeNode*> nodeStack;
        TreeNode* lastNode = nullptr;
    
        while (!nodeStack.empty() or node != nullptr) {
            while (node != nullptr) {
                nodeStack.push(node);
                node = node->left;
            }
            node = nodeStack.top();
            nodeStack.pop();
    
            if (lastNode != nullptr and node->val <= lastNode->val) {
                return false;
            }
            lastNode = node;
            node = node->right;
        }
        return true;
    }
};