Validate Binary Search Tree

To validate a Binary Search Tree, I first clarify that every node's value must strictly fall within a specific range defined by its ancestors, not just its immediate parent. A common trap is checking only if left_child < current < right_child, which fails for nodes deeper in the tree that violate the global constraint. For example, a right child of a left subtree might be larger than the root but smaller than its own parent, breaking the BST property globally. I recommend two robust approaches. First, an in-order traversal: since a valid BST produces a strictly increasing sequence when traversed in-order, we can track the previous visited node and ensure the current node is strictly greater. If any node violates this order, the tree is invalid. Alternatively, and perhaps more intuitively for maintaining context, I use recursive range validation. We pass down minimum and maximum allowable values starting with negative and positive infinity. As we traverse left, we update the upper bound to the current node's value; as we traverse right, we update the lower bound. This ensures every node respects the full ancestral path. Both methods run in O(n) time and O(h) space, where h is the tree height. Given Meta's focus on scalable data structures, ensuring the solution handles skewed trees efficiently via tail recursion optimization or iterative stacks would be a strong addition during implementation.