Binary Search TreesProblem 20 of 22
Check whether BST contains Dead end
Problem Statement
Given a BST, check whether it contains a "dead end" or not. A dead end is a leaf node such that we cannot insert any new element after it while maintaining BST property.
A dead end exists when a leaf node's value has both value-1 and value+1 already present in the BST (or value is 1, so value-1 = 0 is invalid).
Example:
Dead End Exists:
8
/ \
5 9
/ \
2 7
/
1
Node 1 is a dead end:
- Cannot insert 0 (invalid for BST with positive integers)
- Cannot insert 2 (already exists as ancestor)
No Dead End:
8
/ \
5 11
/ \
2 7
/
1
Actually, 1 is still a dead end here too!
Approach 1: Brute Force (Check Each Leaf)
Intuition
For each leaf node, check if we can insert value-1 or value+1. If neither is possible, it's a dead end.
Algorithm
- Find all leaf nodes
- For each leaf, check:
- Is value-1 present in tree? (or is value = 1?)
- Is value+1 present in tree?
- If both conditions true for any leaf, dead end exists
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void storeValues(TreeNode root, Set<Integer> values) {
if (root == null) return;
values.add(root.val);
storeValues(root.left, values);
storeValues(root.right, values);
}
private boolean checkDeadEndBruteForce(TreeNode root, Set<Integer> values) {
if (root == null) return false;
// If leaf node
if (root.left == null && root.right == null) {
boolean leftBlocked = (root.val == 1) || values.contains(root.val - 1);
boolean rightBlocked = values.contains(root.val + 1);
if (leftBlocked && rightBlocked) {
return true;
}
}
return checkDeadEndBruteForce(root.left, values) ||
checkDeadEndBruteForce(root.right, values);
}
public boolean isDeadEndBruteForce(TreeNode root) {
Set<Integer> values = new HashSet<>();
storeValues(root, values);
return checkDeadEndBruteForce(root, values);
}
}Complexity Analysis
- Time Complexity: O(n) - Two traversals
- Space Complexity: O(n) - HashSet to store values
Approach 2: Optimal (Range-based Check)
Intuition
Pass down valid ranges while traversing. At each leaf, if the valid range has size 0 (min == max), it's a dead end.
Algorithm
- Start with range [1, infinity]
- For left child, update max to parent-1
- For right child, update min to parent+1
- At leaf, if min > max or min == max == leaf value, dead end
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private boolean isDeadEndHelper(TreeNode root, int minVal, int maxVal) {
if (root == null) return false;
// If leaf node
if (root.left == null && root.right == null) {
return minVal == maxVal;
}
return isDeadEndHelper(root.left, minVal, root.val - 1) ||
isDeadEndHelper(root.right, root.val + 1, maxVal);
}
public boolean isDeadEnd(TreeNode root) {
return isDeadEndHelper(root, 1, Integer.MAX_VALUE);
}
}Complexity Analysis
- Time Complexity: O(n) - Single traversal
- Space Complexity: O(h) - Recursion stack only
Approach 3: Using Two Sets (Leaves and Non-Leaves)
Intuition
Store leaf nodes in one set and all nodes (including internal) in another. A leaf is dead end if both neighbors exist in the all-nodes set (or leaf is 1).
Algorithm
- Collect all leaf node values
- Collect all node values
- For each leaf, check if val-1 and val+1 are "blocked"
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void collectNodes(TreeNode root, Set<Integer> leaves,
Set<Integer> all) {
if (root == null) return;
all.add(root.val);
if (root.left == null && root.right == null) {
leaves.add(root.val);
}
collectNodes(root.left, leaves, all);
collectNodes(root.right, leaves, all);
}
public boolean isDeadEndTwoSets(TreeNode root) {
Set<Integer> leaves = new HashSet<>();
Set<Integer> all = new HashSet<>();
all.add(0); // Handle val=1 case
collectNodes(root, leaves, all);
for (int leaf : leaves) {
if (all.contains(leaf - 1) && all.contains(leaf + 1)) {
return true;
}
}
return false;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n) - Two sets
Approach 4: Find Dead End Value
Intuition
If we need to return which node is the dead end, modify the approach to return the dead end value.
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int findDeadEnd(TreeNode root, int minVal, int maxVal) {
if (root == null) return -1;
if (root.left == null && root.right == null) {
if (minVal == maxVal) {
return root.val;
}
return -1;
}
int leftResult = findDeadEnd(root.left, minVal, root.val - 1);
if (leftResult != -1) return leftResult;
return findDeadEnd(root.right, root.val + 1, maxVal);
}
public int getDeadEnd(TreeNode root) {
return findDeadEnd(root, 1, Integer.MAX_VALUE);
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(h)
Key Takeaways
- Dead end definition: Leaf where no insertion is possible
- Range-based approach: Most elegant - track valid insertion range
- Range collapse: Dead end when min == max at a leaf
- Positive integers: Assumption that BST values are positive (1 is boundary)
- Set approach: Intuitive but uses more space
- The range-based approach is cleanest and most space-efficient
- Can extend to find ALL dead ends by collecting them instead of returning early