BST with Dead End | Practice Easy 0 attempts
GeeksforGeeks ↗

BST with Dead End | Practice

Easy TreeBinary TreeDFS GeeksforGeeks

Given a BST containing only positive integers, check whether it has a dead end — a leaf node where no new element can be inserted.

Example: BST with nodes {8, 5, 2, 7, 11, 1, 3} → true (node 1 is dead end: can't insert 0 or 2)

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^4
  • 1 <= Node.val <= 10^4
Topics
TreeBinary TreeDFS

DFS with Range Tracking

Track valid range [low, high] for each node. A leaf is a dead end if low == high.

function isDeadEnd(root) {
  function dfs(node, lo, hi) {
    if (!node) return false;
    if (lo === hi) return true;
    return dfs(node.left, lo, node.val - 1) || dfs(node.right, node.val + 1, hi);
  }
  return dfs(root, 1, Infinity);
}

Time: O(n) | Space: O(h)

Saved in this browser only. Private to you.

JavaScript