Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

This problem is fundamental to understanding tree data structures and is a common precursor to more complex tree-related algorithms.

Problem Description

You are tasked with writing a function that takes the root of a binary tree as input and returns True if the tree is a valid Binary Search Tree, and False otherwise.

Key Requirements:

1. Left Subtree Property: For every node, all values in its left subtree must be strictly less than the node's value.
2. Right Subtree Property: For every node, all values in its right subtree must be strictly greater than the node's value.
3. Recursive Validity: Both the left and right subtrees must themselves be valid Binary Search Trees.

Expected Behavior:

• The function should traverse the tree and check if the BST properties hold true for all nodes.
• If at any point a violation of the BST properties is found, the function should immediately return False.
• If the entire tree is traversed without finding any violations, the function should return True.

Edge Cases to Consider:

• Empty Tree: An empty tree (represented by a null root) is considered a valid BST.
• Single Node Tree: A tree with only one node is a valid BST.
• Duplicate Values: The definition of a BST typically disallows duplicate values. Your implementation should adhere to this (i.e., left child < parent, right child > parent).

Examples

Example 1:

Input:
    2
   / \
  1   3

Tree Representation: Node(2, left=Node(1), right=Node(3))

Output: True

Explanation: The root node is 2. Its left child is 1 (1 < 2), and its right child is 3 (3 > 2). Both the left and right subtrees (which are single nodes) are valid BSTs.

Example 2:

Input:
    5
   / \
  1   4
     / \
    3   6

Tree Representation: Node(5, left=Node(1), right=Node(4, left=Node(3), right=Node(6)))

Output: False

Explanation: The root node is 5. Its left child is 1 (1 < 5), which is fine. However, its right child is 4. While 4 < 5, the right subtree of node 4 contains node 6, which is greater than 4. Crucially, node 4 itself is in the right subtree of node 5, but 4 is not greater than 5. Therefore, the BST property is violated.

Example 3:

Input:
    5
   / \
  4   6
     / \
    3   7

Tree Representation: Node(5, left=Node(4), right=Node(6, left=Node(3), right=Node(7)))

Output: False

Explanation: The root node is 5. The left child is 4 (4 < 5). The right child is 6 (6 > 5). However, the left child of node 6 is 3. Node 3 is in the right subtree of node 5, but 3 is less than 5, violating the BST property that all nodes in the right subtree must be greater than the root.

Constraints

• The number of nodes in the tree will be between 0 and 10^4.
• The value of each node will be an integer between -2^31 and 2^31 - 1.
• Your solution should aim for an efficient time complexity, ideally O(N), where N is the number of nodes in the tree.
• The space complexity should also be considered, aiming for O(H) where H is the height of the tree (for recursion stack) or O(1) if an iterative approach is used.

Notes

• Consider how to pass down the valid range of values for each node as you traverse the tree.
• A recursive approach often simplifies the logic, but be mindful of the call stack depth.
• An in-order traversal of a valid BST will produce a sorted sequence of its node values. This observation can be a useful hint for an alternative approach.