BST with Dead End

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Check if BST has a dead end: a leaf node where we cannot insert any new node. Track valid insertion range at each node.

Algorithm

1DFS passing [minVal, maxVal] range. At leaf: dead end if maxVal - minVal == 1.

Common Pitfalls

•Start range [1, INF] (positive integers only). Dead end when no integer fits between min and max.

BST with Dead End.java

Java

// Approach: DFS with [min, max] range for each node. A dead end exists when min+1 == max.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {
    public boolean isDeadEnd(Node root) {
        return f(root, GUB, GLB);
    }

    int GUB = (int) 1e5 + 1; // GLOBAL UPPER BOUND
    int GLB = 0; // GLOBAL LOWER BOUND

    public boolean f(Node root, int UB, int LB) {
        if (root == null)
            return false; // here false is ok as our logic will try to find answer from other end
        if (root.left == null && root.right == null) {
            if (root.data - LB == 1 && UB - root.data == 1)
                return true; // means no element can be inserted
            return false;
        }
        return f(root.left, root.data, LB) || f(root.right, UB, root.data);
    }
}

Was this solution helpful?