439. Check Whether a BST Contains a Dead End

Given a binary search tree containing only positive integers, print 'Yes' if it has a 'dead end' - a leaf value L such that no new node could ever be inserted as its child without breaking the BST property (this happens exactly when L is sandwiched with no room to spare: the tightest lower bound allowed at L is L-1 and the tightest upper bound is L+1) - 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 BST ('N' marks an absent child); all values are positive integers. Output: Print 'Yes' if the BST contains a dead end, otherwise print 'No'.

1 <= number of nodes <= 10^5, all values are positive integers

Only LEAVES can ever be dead ends - any internal node already has at least one child occupying part of its range, meaning its full range was never available for insertion in the first place, so internal nodes never need to be checked.

Check whether a BST (with only positive integer values) has any leaf so tightly squeezed between its ancestors' bounds that no new value could ever be inserted there. Brute force: For every leaf, try actually attempting to insert every possible value directly and check if it would violate the BST property - this is wasteful compared to directly computing the leaf's allowed range and checking its width. Optimised: Tracking the valid (low, high) range during a single descent (the same technique used for BST validation) directly tells you, at each leaf, EXACTLY what values could still be inserted there - checking if that range has been squeezed down to exactly one gap on each side (both a difference of 1) is a simple, direct O(1) check per leaf.

Find every leaf node in the BST, and for each leaf independently walk down from the root again along the path to that leaf, tracking the tightest lower and upper bound implied by the branching decisions made so far (going left tightens the upper bound to the parent's value, going right tightens the lower bound). A leaf value L is a dead end exactly when the tightest lower bound at L equals L-1 and the tightest upper bound equals L+1, since then there is no positive integer that could be legally inserted as its child. Recomputing the root-to-leaf path separately for every leaf makes this quadratic in the worst case (a skewed tree with many leaves each requiring a long walk). Time: O(n^2) Space: O(h) per leaf walk

Do one DFS from the root carrying the currently valid (low, high) range for the node being visited, starting at (0, infinity) since all values are positive (so 0 is never a valid insertable value). Recurse left with range (low, node.val) and right with range (node.val, high). At any leaf, it's a dead end exactly when high - low == 2 (equivalently low == node.val - 1 and high == node.val + 1), meaning no room remains for a new positive-integer child. This achieves the same linear time as the hashing approach but only needs the recursion stack, with no auxiliary hash set. Time: O(n) Space: O(h) recursion stack

Traverse the tree once and insert every node's value into a hash set, O(n). Then traverse again, and for every leaf value L, check the dead-end condition using set membership: if L equals 1 and the set contains 2, it's a dead end (since 0 isn't a valid positive-integer child); otherwise it's a dead end exactly when the set contains both L-1 and L+1. This replaces bound-tracking with direct membership tests, at the cost of the extra hash set. Time: O(n) Space: O(n)

1. Track a valid (low, high) range for every node as you descend, starting from (0, infinity) at the root (since values are positive integers, the true floor is 0). 2. A LEAF is a dead end exactly when (its value - its range's low) equals 1 AND (its range's high - its value) equals 1 - meaning there's no integer left in either gap for a new node to be inserted. 3. Check every leaf this way; if any leaf qualifies, answer Yes.

Time: O(n) - one single traversal, checking each leaf's range once. Space: O(h) for the recursion stack.

Test with a single-node tree (can never be a dead end since its upper bound is unbounded), a leaf with value 1 (its lower bound starts at 0, so only the upper gap needs to be tight), and a tree with 10^5 nodes for performance.

Be precise about the true lower bound being 0 (not negative infinity), since the problem specifies all values are POSITIVE integers - using the wrong floor value would cause an incorrect dead-end check near small values.