Check whether a BST contains a dead end

Medium

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: true

Leaf 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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}