package binarytree;

import datastructures.tree.BinarySearchTree;
import datastructures.tree.TreeNode;

public class CheckBSTHasDeadEnd {
  private BinarySearchTree<Integer> tree = null;
  private TreeNode<Integer> root = null;

  public CheckBSTHasDeadEnd() {
    tree = new BinarySearchTree<Integer>();
  }

  public void constructTree(String[] input) {
    for (String line : input) {
      String[] values = line.split(" ");
      String action = values[0];

      switch (action) {
      case "insertRoot":
        tree = new BinarySearchTree<Integer>();
        root = tree.insertRoot(Integer.parseInt(values[1]));
        break;
      case "insert":
        tree.insert(root, Integer.parseInt(values[1]));
        break;
      }
    }
  }

  public boolean hasDeadEnd() {
    return hasDeadEnd(root, new Range(0, Integer.MAX_VALUE));
  }

  private boolean hasDeadEnd(TreeNode<Integer> root, Range range) {
    if(root == null) {
      return false;
    } else if (root.left == null && root.right == null) {
      return Math.abs(root.data - range.min) <= 1 && Math.abs(range.max - root.data) <= 1;
    } else {
      return hasDeadEnd(root.left, new Range(range.min, root.data)) || hasDeadEnd(root.right, new Range(root.data, range.max));
    }
  }

  private class Range {
    private int min;
    private int max;

    Range(int min, int max) {
      this.min = min;
      this.max = max;
    }
  }
}

@@ -97,16 +97,150 @@
 eNode;%0A%0A
+/**%0A * Question:%0A * http://www.geeksforgeeks.org/check-whether-bst-contains-dead-end-not/%0A * %0A * @author Sudharsanan Muralidharan%0A */%0A
 public c
@@ -1047,16 +1047,17 @@
 %7B%0A    if
+ 
 (root ==
@@ -1314,16 +1314,26 @@
 t.data))
+%0A         
  %7C%7C hasD

Add question link :P