How do you determine if a given binary tree is a valid Binary Search Tree (BST)?

You are given the definition of a binary tree node:

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Write a function is_bst(root) that takes the root of a binary tree as input and returns True if the tree is a valid Binary Search Tree (BST), and False otherwise.

Definition of a BST:

• 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.

Example 1:

Input: root = [2,1,3]
Output: true

2
   / \
  1   3

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false

    5
   / \
  1   4
     / \
    3   6
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, 10000].
• -10000 <= Node.val <= 10000

Your solution should handle edge cases such as an empty tree or a tree with only one node.

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# Naive Solution
# Check for each node if its value is greater than all values in the left subtree
# and smaller than all values in the right subtree
# This involves traversing the entire left and right subtrees for each node

def is_bst_naive(root):
    if not root:
        return True

    def get_max(node):
        if not node:
            return float('-inf')
        return max(node.val, get_max(node.left), get_max(node.right))

    def get_min(node):
        if not node:
            return float('inf')
        return min(node.val, get_min(node.left), get_min(node.right))

    if (root.left and get_max(root.left) >= root.val) or (root.right and get_min(root.right) <= root.val):
        return False

    return is_bst_naive(root.left) and is_bst_naive(root.right)


# Optimal Solution
# Use the concept of range. For each node, check if its value is within the valid range
# The valid range is determined by the values of its ancestors

def is_bst(root):
    def is_bst_helper(node, min_val, max_val):
        if not node:
            return True

        if (min_val is not None and node.val <= min_val) or (max_val is not None and node.val >= max_val):
            return False

        return is_bst_helper(node.left, min_val, node.val) and is_bst_helper(node.right, node.val, max_val)

    return is_bst_helper(root, None, None)


# Example Usage:

# Example 1
root1 = Node(2, Node(1), Node(3))
print(f"Is BST: {is_bst(root1)}")  # Output: True

# Example 2
root2 = Node(5, Node(1), Node(4, Node(3), Node(6)))
print(f"Is BST: {is_bst(root2)}")  # Output: False

# Example 3: Single node tree
root3 = Node(10)
print(f"Is BST: {is_bst(root3)}") # Output: True

# Example 4: Empty tree
root4 = None
print(f"Is BST: {is_bst(root4)}") # Output: True

# Example 5:
root5 = Node(5, Node(4), Node(6, Node(3), Node(7)))
print(f"Is BST: {is_bst(root5)}") # Output: False

Big(O) Runtime Analysis of is_bst (Optimal Solution):

• The is_bst function uses a helper function is_bst_helper which performs a depth-first traversal of the binary tree.
• Each node in the tree is visited exactly once.
• At each node, a constant amount of work is done (comparison with min_val and max_val).
• Therefore, the time complexity is directly proportional to the number of nodes in the tree.
• Big(O) Runtime: O(N), where N is the number of nodes in the tree.

Big(O) Space Usage Analysis of is_bst (Optimal Solution):

• The space complexity is determined by the call stack due to the recursive calls to is_bst_helper.
• In the worst-case scenario (a skewed tree), the recursion depth can be equal to the number of nodes in the tree (N).
• In the best-case scenario (a balanced tree), the recursion depth is logarithmic, O(log N).
• Big(O) Space: O(H), where H is the height of the tree. In the worst case, this becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Edge Cases:

1. Empty Tree:
   • If the root is None, the function should return True because an empty tree is a valid BST.
2. Single Node Tree:
   • If the tree contains only one node, the function should return True because a single node tree is a valid BST.
3. Duplicate Values:
   • The problem statement implies strict BST property (left < node < right). If duplicate values are allowed (left <= node <= right), the comparison operators need to be adjusted accordingly.
4. Integer Overflow:
   • If node values can be very large or very small, there's a potential for integer overflow when comparing against min_val and max_val. Consider using a larger data type or a different approach if this is a concern.
5. Skewed Tree (Worst-Case Space Complexity):
   • For a highly skewed tree (where all nodes are only in one branch), the recursive calls can lead to a stack overflow if the tree is extremely large. This can be mitigated using an iterative approach with an explicit stack.
6. Values equal to min_val or max_val:
   • The condition (min_val is not None and node.val <= min_val) or (max_val is not None and node.val >= max_val) correctly handles cases where node.val is equal to min_val or max_val. In a valid BST, all nodes in the left subtree should be strictly less than the current node and all nodes in the right subtree should be strictly greater than the current node.