Check whether BST contains Dead End or not

Given a Binary search Tree that contains positive integer values greater then 0. The task is to check whether the BST contains a dead end or not. Here Dead End means, we are not able to insert any element after that node.

A simple approach is to check if there is a leaf node with value v such that v+1 and v-1 exist in BST with exception of v = 1. Cause for v=1, we can't insert 0 as BST contains positive integers only. We first do traversal to store all nodes, and also store leaf nodes in another hash map. Time complexity is O(n).

Another method is to track the range for subtree, if the size of the subtree within the range is 1, then we found a dead end.

bool BinarySearchTree::isDeadEndUtil(TreeNode *root, int left, int right) {
    if (!root) return false;
    if (right - left == 2) return true;

    return isDeadEndUtil(root->left, left, root->val) || isDeadEndUtil(root->right, root->val, right);
}

bool BinarySearchTree::isDeadEnd(TreeNode *root) {
    return isDeadEndUtil(root, 0, INT_MAX);
}