Check whether a BST contains a dead end
Problem
The BST holds positive integers. A dead end is a leaf where no new value can be inserted, because both value − 1 and value + 1 are already taken (treat 0 as taken). Return true if the BST contains a dead end.
Example 1
Input: BST {8, 5, 2, 3, 7, 11, 4}
Output: trueLeaf 4: 3 and 5 are both present.
Also asked as: Check whether BST contains Dead end
Test cases
Case 1
Input: [8,5,11,2,7,null,null,null,3,null,null,null,4] Expected: true
Case 2
Input: [8,7,10,2,null,9,13] Expected: true
Case 3
Input: [5,3,8] Expected: false
Case 4
Input: [1] Expected: false
View solutionHide solution1 approach
1. Track the allowed (lo, hi) window; a leaf with hi − lo === 2 is a dead end
Time O(n)Space O(h)
A dead-end leaf value v can’t accept any new node because both v−1 and v+1 are boundaries. That happens exactly when the leaf’s open interval is (v−1, v+1).
function hasDeadEnd(root, lo = 0, hi = Infinity) { if (!root) return false; if (!root.left && !root.right) return root.val - lo === 1 && hi - root.val === 1; return hasDeadEnd(root.left, lo, root.val) || hasDeadEnd(root.right, root.val, hi);}