BST with Dead End | Practice Easy 0 attempts
GeeksforGeeks ↗

BST with Dead End | Practice

Easy TreeBinary TreeDFS GeeksforGeeks

You're given a binary search tree whose values are all positive integers. Determine whether it contains a dead end — a leaf whose value v is boxed in on both sides, meaning neither v - 1 nor v + 1 (bounded below by 1) could ever be inserted into the tree without violating the BST property.

Input Format
Implement isDeadEnd(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
root = [8,5,11,2,7,null,null,1,3]
Output
true

Example 2

Input
root = [8,5,11]
Output
false
Constraints
  • 1 <= N <= 10^4
  • 1 <= Node.val <= 10^4
Test Cases (2)
Case 1
Args: [[8,5,11,2,7,null,null,1,3]] Expected: true
Case 2
Args: [[8,5,11]] Expected: false
Topics
TreeBinary TreeDFS

Iterative Range Tracking

Each node has an inclusive range of allowed positive integers. When the lower and upper bounds are equal, no further value can be inserted below that node.

javascript
function isDeadEnd(root) {
  const stack=root?[[root,1,Infinity]]:[];
  while(stack.length){const [node,lo,hi]=stack.pop();if(lo===hi)return true;if(node.left)stack.push([node.left,lo,node.val-1]);if(node.right)stack.push([node.right,node.val+1,hi]);}
  return false;
}

Time: O(n) | Space: O(h) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript