Check whether BST contains Dead end

The problem, simply

You get a binary search tree (BST) that holds only whole numbers bigger than 0, with no repeats. A leaf (a spot with no children) is a dead end if you can never insert any new number under it.

Under a leaf x you could hang x - 1 on the left or x + 1 on the right, or anything else that still fits the BST rules on the way down. A dead end is a leaf where the only number that fits its spot is x itself. Say true if the tree has a dead end.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write down every number in a set, and also write down 0 (because 0 is not allowed, it acts as "taken"). Then look at every leaf x: if both x - 1 and x + 1 are in the set, it is a dead end.

Why this works: for a leaf x, the closest taken numbers on each side are on its road from the top. If x - 1 and x + 1 are both taken, the leaf's range is only x.

import java.util.*;

class Solution {
    public boolean isDeadEnd(TreeNode root) {
        Set<Integer> taken = new HashSet<>();
        Set<Integer> leaves = new HashSet<>();
        taken.add(0);                                // 0 is not allowed, so treat it as taken
        collect(root, taken, leaves);
        for (int x : leaves) {
            if (taken.contains(x - 1) && taken.contains(x + 1)) return true;
        }
        return false;
    }

    private void collect(TreeNode node, Set<Integer> taken, Set<Integer> leaves) {
        if (node == null) return;
        taken.add(node.val);
        if (node.left == null && node.right == null) leaves.add(node.val);
        collect(node.left, taken, leaves);
        collect(node.right, taken, leaves);
    }
}

How long it takes: every spot once, plus one check per leaf, O(n). Extra room: the two sets, O(n).

Way 2: the clever way

Do not store anything. Carry the range of allowed numbers down the tree, like the BST check.

1. The top gets [1, infinity].
2. Going left from x, the high end becomes x - 1.
3. Going right from x, the low end becomes x + 1.
4. At a leaf, if low == high, only the leaf itself fits there. Dead end.

class Solution {
    public boolean isDeadEnd(TreeNode root) {
        return check(root, 1, Integer.MAX_VALUE);
    }

    // low and high: the numbers that could still land in this spot
    private boolean check(TreeNode node, int low, int high) {
        if (node == null) return false;
        if (node.left == null && node.right == null) return low == high;
        return check(node.left, low, node.val - 1)
            || check(node.right, node.val + 1, high);
    }
}

How long it takes: every spot once in the worst case, O(n). Extra room: only the recursion, O(h).

Watch out for

• Checking x - 1 and x + 1 against the leaf's parent only. The taken neighbor can be far up the road, like 8 for leaf 9.
• If the problem allowed 0 or negative numbers, the left end would never block. Ask what the smallest allowed number is.
• Returning at the first leaf. Use || so the walk keeps going until a dead end is found.

What interviewers ask next

• Return every dead end, not just whether one exists. Collect the leaves where low == high into a list.
• Count how many numbers can still be inserted under each leaf. It is high - low, the size of the range minus the leaf itself.
• Can a spot that is not a leaf be "full"? Yes, if its range has no room on one side, but then it still has a child. The question only asks about leaves.
• How does this relate to validating a BST? Same idea: pass a window down and tighten it, with - 1 and + 1 because the numbers are whole and distinct.

Remember this

Grown-up words: the stretch of house numbers is the range or bounds, carrying it down is depth first search with bounds, a spot with no children is a leaf node, and treating 0 as taken is a sentinel value.