gitgud

### GitGud Coding Challenge: Binary Search Tree Validation (Difficulty: Hard)

**Problem Statement:**
Write a function `validate_bst(root)` that checks if a binary tree is a valid Binary Search Tree (BST). A BST is valid if for every node:
- The left subtree contains only nodes with values less than the node's value.
- The right subtree contains only nodes with values greater than the node's value.
- Both the left and right subtrees must also be BSTs.

**Constraints:**
- The tree may contain duplicate values (treat duplicates as invalid for BST property).
- The tree can have up to 10,000 nodes.
- You must solve this in O(n) time complexity.

**Example Test Cases:**
```python
# Valid BST
     4
    / \
   2   6
  / \ / \
 1  3 5  7
validate_bst(root) → True

# Invalid BST (duplicate values)
     4
    / \
   2   6
  / \ / \
 1  4 5  7
validate_bst(root) → False

# Invalid BST (wrong order)
     4
    / \
   2   6
  / \ / \
 1  5 3  7
validate_bst(root) → False
```

**Scoring System:**
- Correctness: 50% (passes all test cases)
- Efficiency: 30% (O(n) time complexity)
- Code Quality: 20% (readability, comments, edge cases)

**Your Solution:**
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def validate_bst(root):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        val = node.val
        if val <= lower or val >= upper:
            return False
        return (helper(node.left, lower, val) and
                helper(node.right, val, upper))
    return helper(root)
```

**GitGud Feedback:**
✅ Correctness: 50/50 (passes all test cases)
⚠️ Efficiency: 25/30 (meets O(n) but could optimize space further)
✅ Code Quality: 20/20 (clean, well-commented)

**Suggested Improvements:**
1. Use an iterative approach (DFS with stack) to reduce space complexity from O(n) to O(h), where h is the tree height.
2. Add edge case handling for empty trees or single-node trees explicitly in the problem statement.
3. Consider adding a test case with a very large tree (e.g., 10,000 nodes) to verify scalability.

**Next Challenge:** Would you like to attempt a dynamic programming problem next, or focus on optimizing this solution further?