Amazon Interview Question Senior Software Development Engineers
Country: India
Interview Type: In-Person
say the BST cannot have two particular value like -1 and 0
Then following method solves it. It's a binary search tree if the method does not return -1
public int preOrd(Node root){
if(root==null){
return 0;
}
int val = root.getValue();
int lVal=preOrd(root.getLChild);
int rVal=preOrd(root.getRChild);
if(lVal==-1){
return -1;
}
if(rVal==-1){
return -1;
}
if(lVal!=0&&lVal>val){
return -1;
}
if(rVal!=0&&rVal<val){
return -1;
}
return val;
}
Following method solves this. If it returns null, that means it is not a BST.
public ArrayList<Integer> inOrder(Node root){
if(root==null){
return new ArrayList<Integer>();
}
ArrayList<Integer> leftNodes = inOrder(root.getLChild());
if(leftNodes!=null){
int size=leftNodes.size();
if(size>0){
Node last = leftNodes.get(size-1);
if(last.getValue()>root.getValue()){
return null;
}
}
leftNodes.add(root);
}else{
return null;
}
ArrayList<Integer> rightNodes = inOrder(root.getRChild());
if(rightNodes!=null){
int size=rightNodes.size();
if(size>0){
Node first = rightNodes.get(0);
if(first.getValue()<root.getValue()){
return null;
}
}
leftNodes.addAll(rightNodes);
}else{
return null;
}
return leftNodes;
}
I would propose the following: If the binary tree is BST, at any given node as a root, it has the following properties:
(i) The left most node in the right subtree is greater or equal to the root.
(ii) The right most node in the left subtree is less than a root.
Given the root of a binary tree one can recursively check for these two properties. A sample code is shown below:
public static boolean isBST(Node root) {
return checkLeft(root, root.val) && checkRight(root, root.val);
}
private static boolean checkRight(Node x, int val) {
if (x == null) return true;
if (x < val) return false;
return checkRight(x.right, val);
}
private static boolean checkLeft(Node x, int val) {
if (x == null) return true;
if (x >= val) return false;
return checkLeft(x.right, val);
}
public boolean isBST(Node n) {
if (n == null) {
return true;
}
Node left, right;
left = n.left;
right = n.right
boolean leftCondition, rightCondition;
leftCondition = (left == null) ? true : (left.value < n.value) ? true : false;
rightCondition = (right == null) ? true : (right.value > n.value) ? true : false;
return leftCondition && rightCondition && isBST(n.left) && isBST(n.right);
}
Following method solves this. If it returns null, that means it is not a BST.
public ArrayList<Integer> inOrder(Node root){
if(root==null){
return new ArrayList<Integer>();
}
ArrayList<Integer> leftNodes = inOrder(root.getLChild());
if(leftNodes!=null){
int size=leftNodes.size();
if(size>0){
Node last = leftNodes.get(size-1);
if(last.getValue()>root.getValue()){
return null;
}
}
leftNodes.add(root);
}else{
return null;
}
ArrayList<Integer> rightNodes = inOrder(root.getRChild());
if(rightNodes!=null){
int size=rightNodes.size();
if(size>0){
Node first = rightNodes.get(0);
if(first.getValue()<root.getValue()){
return null;
}
}
leftNodes.addAll(rightNodes);
}else{
return null;
}
return leftNodes;
}
At any given node, pass along the valid range of the node's value.
When you recurse left and right, constrain the range.
Ex. something like this (note that the edge cases aren't quite correct here as they assume distinct values, but this is easy to change and depends on your definition of the BST)
boolean isBST(Node n) {
return isBST(n, Integer.MIN, Integer.MAX);
}
boolean isBST(Node n, int left, int right) {
if (n.val < left || n.val > right) {
return false;
}
return isBST(n.left, left, n.val - 1) && isBST(n.right, n.val + 1, right);
}
Go on parsing till you get a condition which tells you that the tree isn't sorted
private boolean isTreeBST(Node root) {
if (root == null) return true;
if (root.getLeft() != null &&
root.getValue() < root.getLeft().getValue()) {
return false;
}
if (root.getRight() != null &&
root.getValue() > root.getRight().getValue()) {
return false;
}
if(!isTreeBST(root.getLeft()) ||
!isTreeBST(root.getRight())) {
return false;
}
return true;
}
package in.blogspot.randomcompiler;
class TreeNode {
int data;
TreeNode left;
TreeNode right;
}
public class CheckBST {
public static void main(String[] args) {
TreeNode n1 = new TreeNode();
n1.data = 100;
TreeNode n2 = new TreeNode();
n2.data = 75;
n1.left = n2;
TreeNode n3 = new TreeNode();
n3.data = 125;
n1.right = n3;
TreeNode n4 = new TreeNode();
n4.data = 50;
n2.left = n4;
TreeNode n5 = new TreeNode();
n5.data = 90;
n2.right = n5;
System.out.println(isBST(n1));
}
private static boolean isBST(TreeNode root) {
if(root == null) return true;
boolean isBSTLeft = isBST(root.left);
boolean isBSTRight = isBST(root.right);
boolean gtLeft = root.left == null? true : root.data >= root.left.data;
boolean ltRight = root.right == null? true : root.data < root.right.data;
return isBSTLeft && isBSTRight && gtLeft && ltRight;
}
}
Output:
true
bool CheckBST(node *root)
{
Bool left,right;
if (root==NULL)
return (1);
if (root->right !=NULL && getLeft(root-right) < root->value)
return 0;
if (root->left !=NULL && getRight(root->left) > root->value)
return 0;
left=CheckBST(root->left);
right=CheckBST(root->right);
return (left && right);
}
int getLeft(node *root)
{
int val = root->value;
while (root->left!=NULL)
{
root= root->left;
val = root->value;
}
return val;
}
int getRight(node *root)
{
int val = root->value;
while (root->right!=NULL)
{
root= root->right;
val = root->value;
}
return val;
}
{
isBST(Node root){
RetVal lRet = isBST(root.left());
if(!lRet.isBST())
return new RetVal(false,null,null);
RetVal rRet = isBST(root.right());
if(!rRet.isBST())
return new RetVal(false,null,null);
if((lRet.max()==null || lRet.max().value() <= root.value())
&&(rRet.min()==null || rRet.min().value() >= root.value()))
return new RetVal(true, lRet.min()!=null?lRet.min():root ,rRet.max()!=null? rRet.max():root);
return new RetVal(false,null,null);
}
}
public class IsBST {
public static boolean isBST(TreeNode node) {
if(node.left == null & node.right == null) {
return true;
} else if(node.left == null ) {
isBST(node.right);
} else if(node.right == null ) {
isBST(node.left);
} else {
return Integer.parseInt(node.left.data) < Integer.parseInt(node.data) && Integer.parseInt(node.right.data) > Integer.parseInt(node.data) ?
isBST(node.right) && isBST(node.left) :false;
}
return false;
}
}
A binary tree is a BST if and only if:
1. The left sub tree is a BST.
2. The right sub tree is a BST.
3. The left sub tree is null, or the maximum value of the left sub tree is smaller or equal to the node value.
4. The right sub tree is null, or the minimum value of the right sub tree is larger or equal to the node value.
- Omri Bashari May 03, 2015bool is_bst(node_t* n, int& min_val, int& max_val) { if (nullptr == n) return true; int min_sub = std::numeric_limits<int>::max(); int max_sub = -std::numeric_limits<int>::max(); if (!is_bst(n->left, min_sub, max_sub) || max_sub > n->value) return false; min_val = min_sub; if (!is_bst(n->right, min_sub, max_sub) || min_sub < n->value) return false; max_val = max_sub; min_val = std::min(min_val, n->value); // in case n->left is nullptr max_val = std::max(max_val, n->value); // in case n->right is nullptr return true; }