Validate Binary Search Tree

A Binary Search Tree (BST) is a tree data structure where the value of each node is greater than all values in its left subtree and less than all values in its right subtree. This property must hold for every node in the tree to be considered a valid BST. This challenge asks you to write an algorithm to determine if a given binary tree is a valid BST.

Problem Description

You are given the root node of a binary tree. Your task is to determine if the tree is a valid Binary Search Tree (BST). A valid BST must adhere to the following rules:

• The left subtree of a node contains only nodes with values less than the node's value.
• The right subtree of a node contains only nodes with values greater than the node's value.
• The root node's left and right subtrees must also be valid BSTs.

You need to implement a function that takes the root node of the binary tree as input and returns true if the tree is a valid BST, and false otherwise.

Key Requirements:

• Handle empty trees gracefully (an empty tree is considered a valid BST).
• Consider the case where duplicate values are present. The problem statement does not specify how to handle duplicates; you must clearly define your approach in your solution (e.g., strictly less than, strictly greater than, allow equality in either subtree). State your assumption clearly in your solution.
• The solution should be efficient.

Expected Behavior:

The function should traverse the tree and check the BST property at each node. If any node violates the BST property, 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.
• Tree with only one node.
• Trees with skewed structures (left-skewed or right-skewed).
• Trees with duplicate values (handle according to your chosen approach).
• Large trees to ensure performance.

Examples

Example 1:

Input:
    2
   / \
  1   3

Output: true Explanation: The tree is a valid BST. All nodes satisfy the BST property.

Example 2:

Input:
    5
   / \
  1   4
     / \
    3   6

Output: false Explanation: Node 3 is in the right subtree of node 4, but 3 < 4. This violates the BST property.

Example 3:

Input:
    1
   / \
  2   3

Output: false Explanation: Node 2 is in the left subtree of node 1, but 2 > 1. This violates the BST property.

Constraints

• The number of nodes in the tree can range from 0 to 100,000.
• The values of the nodes are integers.
• The tree is represented using a standard binary tree node structure (e.g., Node { value, left, right }).
• The solution should have a time complexity of O(N), where N is the number of nodes in the tree. A solution with O(N log N) is acceptable, but less desirable.
• The solution should have a space complexity of O(H), where H is the height of the tree. In the worst case (skewed tree), H can be N.

Notes

Consider using recursion or an iterative approach with a stack. A common approach is to maintain a lower and upper bound for each node during the traversal. Remember to clearly document your assumptions about how to handle duplicate values. Think about how to efficiently check the BST property without unnecessary traversals.