128. Check if a Binary Tree Is a Valid BST

Given a binary tree, print 'Yes' if it satisfies the binary search tree property (every node's value is strictly greater than every value in its left subtree and strictly less than every value in its right subtree), otherwise print 'No'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens describing the binary tree ('N' marks an absent child). Output: Print 'Yes' if the tree satisfies the BST property, otherwise print 'No'.

1 <= number of nodes <= 10^5

An alternative, equally valid approach is checking that a full INORDER traversal produces strictly increasing values - if it ever doesn't, the tree isn't a valid BST; this avoids needing to think about ranges at all.

Check whether a binary tree actually satisfies the BST property everywhere, not just locally between immediate parent and child. Brute force: Just check that each node's value is bigger than its left child and smaller than its right child directly - this is WRONG, since a node deep within the left subtree could still be larger than the ROOT's value, violating the BST property globally even though every immediate parent-child pair looks fine locally. Optimised: Passing down a shrinking (low, high) valid-range as you recurse correctly captures the GLOBAL constraint (a node's value must respect every ancestor's bound, not just its immediate parent) - this single recursive pass with tightening bounds is both correct and efficient.

A binary tree is a valid BST exactly when its in-order traversal visits values in strictly increasing order, so traverse the tree once in-order, store every value into an array, and then scan that array to confirm it is strictly increasing. This does a single O(n) traversal instead of a traversal per node, a real improvement over the brute approach, but it still pays for an auxiliary array holding every value. Time: O(n) Space: O(n)

Recurse down the tree carrying an allowed (low, high) range for each node: the root's range is unbounded, and when recursing left the high bound tightens to the current node's value while recursing right tightens the low bound. A node is valid only if its value fits strictly inside its inherited range, which enforces the BST property globally rather than just against its immediate children. This needs no auxiliary array of values at all, so space drops to just the recursion stack. Time: O(n) Space: O(h)

For every node in the tree, collect all values in its left subtree and all values in its right subtree via a full traversal, then check that every left value is strictly less than the node and every right value is strictly greater. This directly tests the BST definition at each node, but since every node triggers its own traversal of its whole subtree, the work is repeated over and over as you move up the tree. Time: O(n^2) Space: O(n)

1. Recursively check each node against a valid (low, high) RANGE, not just against its immediate children. 2. When recursing into the left child, tighten the range's upper bound to the current node's value; when recursing into the right child, tighten the range's lower bound. 3. A node fails validation if its value falls outside its current allowed range.

Time: O(n) - one single pass visiting every node exactly once. Space: O(h) for the recursion stack.

Test with a single-node tree (trivially valid), a tree where a deeply nested node violates a distant ancestor's bound rather than its immediate parent's, and a tree with 10^5 nodes for performance.

Be ready to give a concrete counter-example showing why the naive 'check immediate children only' approach fails - this is one of the most common subtle bugs in BST validation, and demonstrating you understand WHY it fails is a strong signal.