98. Validate Binary Search Tree

Validate Binary Search Tree (Medium)
Determine whether a binary tree satisfies the rules of a Binary Search Tree (BST). In a valid BST, every node must have all values in its left subtree strictly less than it and all values in its right subtree strictly greater than it. The key insight is that checking only the direct parent-child relationship is not enough—each node must also respect the constraints imposed by all of its ancestors.

BFS Iterative Solution:
* I did not need to do the for loop to take a snapshot of the level. Because we are not required to process level by level in this problem. What matters is if each node satisfies the boundary.

The BFS approach uses a queue to traverse the tree level by level while storing each node with its allowed (low, high) range. For each node, we verify that low ❮ node.val ❮ high, then push the left child with (low, node.val) and the right child with (node.val, high). This ensures every node respects the constraints from its ancestors.
Time Complexity: O(n)
Space Complexity: O(n)

DFS Recursive Solution:
The DFS recursive approach passes down a valid value range (low, high) for each node. The root begins with (-∞, +∞). When moving to the left child, the upper bound becomes the current node’s value, and when moving to the right child, the lower bound becomes the current node’s value. If a node’s value falls outside its allowed range, the tree is not a valid BST.
Time Complexity: O(n)
Space Complexity: O(h)

Main Trick:
Each node must stay within a valid range inherited from its ancestors, not just be compared with its immediate parent.
Reason for why the Space Complexity of the DFS Recursive solution is O(h):
When a recursive function calls itself, the computer must remember the previous call so it can return to it later. Each of those remembered calls sits on something called the call stack.

So if your recursion goes like this:

root
└─ left
└─ left
└─ left

the stack will look like:

valid(root)
valid(root.left)
valid(root.left.left)
valid(root.left.left.left)

Each call stays in memory until its children finish.

So the maximum number of calls in memory at once equals how far down the tree you go before returning. That distance is the height of the tree (h).
If the tree is skewed however, it can take up to O(n) space worst case.

Видео 98. Validate Binary Search Tree канала JunCodes