Given a Binary Search Tree that contains positive integer values greater than 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 integer element after that node.
Examples:
Input : 8
/
5 9
/
2 7
/
1
Output : Yes
Explanation : Node "1" is the dead End because
after that we cant insert any element.
Input : 8
/
7 10
/ /
2 9 13
Output :Yes
Explanation : We can't insert any element at
node 9.
We have discussed a solution in below post.
Check whether BST contains Dead End or not
The idea in this post is based on method 3 of Check if a binary tree is BST or not.
First of all, it is given that it is a BST and nodes are greater than zero, root node can be in the range [1, ∞] and if root val is say, val, then left sub-tree can have the value in the range [1, val-1] and right sub-tree the value in range [val+1, ∞].
we need to traverse recursively and when the the min and max value of range coincided it means that we cannot add any node further in the tree.
Hence we encounter a dead end.
Following is the simple recursive solution to the problem.
C++
// CPP Program to check if there is a dead end // in BST or not. #include <bits/stdc++.h> using namespace std; // A BST node struct Node { int data; struct Node *left, *right; }; // A utility function to create a new node Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } /* A utility function to insert a new Node with given key in BST */struct Node* insert(struct Node* node, int key) { /* If the tree is empty, return a new Node */ if (node == NULL) return newNode(key); /* Otherwise, recur down the tree */ if (key < node->data) node->left = insert(node->left, key); else if (key > node->data) node->right = insert(node->right, key); /* return the (unchanged) Node pointer */ return node; } // Returns true if tree with given root contains // dead end or not. min and max indicate range // of allowed values for current node. Initially // these values are full range. bool deadEnd(Node* root, int min=1, int max=INT_MAX) { // if the root is null or the recursion moves // after leaf node it will return false // i.e no dead end. if (!root) return false; // if this occurs means dead end is present. if (min == max) return true; // heart of the recursion lies here. return deadEnd(root->left, min, root->data - 1) || deadEnd(root->right, root->data + 1, max); } // Driver program int main() { /* 8 / 5 11 / 2 7 3 4 */ Node* root = NULL; root = insert(root, 8); root = insert(root, 5); root = insert(root, 2); root = insert(root, 3); root = insert(root, 7); root = insert(root, 11); root = insert(root, 4); if (deadEnd(root) == true) cout << "Yes " << endl; else cout << "No " << endl; return 0; } |
Java
// Java Program to check if there // is a dead end in BST or not. class BinarySearchTree { // Class containing left and right // child of current node and key value class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } // Root of BST Node root; // Constructor BinarySearchTree() { root = null; } // This method mainly calls insertRec() void insert(int data) { root = insertRec(root, data); } // A recursive function // to insert a new key in BST Node insertRec(Node root, int data) { // If the tree is empty, // return a new node if (root == null) { root = new Node(data); return root; } /* Otherwise, recur down the tree */ if (data < root.data) root.left = insertRec(root.left, data); else if (data > root.data) root.right = insertRec(root.right, data); /* return the (unchanged) node pointer */ return root; } // Returns true if tree with given root contains // dead end or not. min and max indicate range // of allowed values for current node. Initially // these values are full range. boolean deadEnd(Node root, int min, int max) { // if the root is null or the recursion moves // after leaf node it will return false // i.e no dead end. if (root==null) return false; // if this occurs means dead end is present. if (min == max) return true; // heart of the recursion lies here. return deadEnd(root.left, min, root.data - 1)|| deadEnd(root.right, root.data + 1, max); } // Driver Program public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* 8 / 5 11 / 2 7 3 4 */ tree.insert(8); tree.insert(5); tree.insert(2); tree.insert(3); tree.insert(7); tree.insert(11); tree.insert(4); if (tree.deadEnd(tree.root ,1 , Integer.MAX_VALUE) == true) System.out.println("Yes "); else System.out.println("No " ); } } // This code is contributed by Gitanjali. |
Python3
# Python 3 Program to check if there
# is a dead end in BST or not.
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# A utility function to insert a
# new Node with given key in BST
def insert(node, key):
# If the tree is empty,
# return a new Node
if node == None:
return Node(key)
# Otherwise, recur down the tree
if key < node.data:
node.left = insert(node.left, key)
elif key > node.data:
node.right = insert(node.right, key)
# return the (unchanged) Node pointer
return node
# Returns true if tree with given
# root contains dead end or not.
# min and max indicate range
# of allowed values for current node.
# Initially these values are full range.
def deadEnd(root, Min, Max):
# if the root is null or the recursion
# moves after leaf node it will return
# false i.e no dead end.
if root == None:
return False
# if this occurs means dead
# end is present.
if Min == Max:
return True
# heart of the recursion lies here.
return (deadEnd(root.left, Min, root.data – 1) or
deadEnd(root.right, root.data + 1, Max))
# Driver Code
if __name__ == ‘__main__’:
# 8
# /
# 5 11
# /
# 2 7
#
# 3
#
# 4
root = None
root = insert(root, 8)
root = insert(root, 5)
root = insert(root, 2)
root = insert(root, 3)
root = insert(root, 7)
root = insert(root, 11)
root = insert(root, 4)
if deadEnd(root, 1, 9999999999) == True:
print(“Yes”)
else:
print(“No”)
# This code is contributed by PranchalK
C#
using System; // C# Program to check if there // is a dead end in BST or not. public class BinarySearchTree { // Class containing left and right // child of current node and key value public class Node { private readonly BinarySearchTree outerInstance; public int data; public Node left, right; public Node(BinarySearchTree outerInstance, int item) { this.outerInstance = outerInstance; data = item; left = right = null; } } // Root of BST public Node root; // Constructor public BinarySearchTree() { root = null; } // This method mainly calls insertRec() public virtual void insert(int data) { root = insertRec(root, data); } // A recursive function // to insert a new key in BST public virtual Node insertRec(Node root, int data) { // If the tree is empty, // return a new node if (root == null) { root = new Node(this, data); return root; } /* Otherwise, recur down the tree */ if (data < root.data) { root.left = insertRec(root.left, data); } else if (data > root.data) { root.right = insertRec(root.right, data); } /* return the (unchanged) node pointer */ return root; } // Returns true if tree with given root contains // dead end or not. min and max indicate range // of allowed values for current node. Initially // these values are full range. public virtual bool deadEnd(Node root, int min, int max) { // if the root is null or the recursion moves // after leaf node it will return false // i.e no dead end. if (root == null) { return false; } // if this occurs means dead end is present. if (min == max) { return true; } // heart of the recursion lies here. return deadEnd(root.left, min, root.data - 1) || deadEnd(root.right, root.data + 1, max); } // Driver Program public static void Main(string[] args) { BinarySearchTree tree = new BinarySearchTree(); /* 8 / 5 11 / 2 7 3 4 */ tree.insert(8); tree.insert(5); tree.insert(2); tree.insert(3); tree.insert(7); tree.insert(11); tree.insert(4); if (tree.deadEnd(tree.root,1, int.MaxValue) == true) { Console.WriteLine("Yes "); } else { Console.WriteLine("No "); } } } // This code is contributed by Shrikant13 |
Output:
Yes
leave a comment
0 Comments