Check if a given tree is a val

Facebook Interview Question for Software Engineer / Developers

0

of 2 votes

33
Answers
Check if a given tree is a valid BST
- tbag October 26, 2013 in United States | Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm

Email me when people comment.

An error occurred in subscribing you.

Country: United States
Interview Type: Phone Interview

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 12 vote

/* Check for binary tree whether its binary search tree */
	private static boolean isBST(BSTNode root, int prev) {
		if(root==null)
			return true;
		if(!isBST(root.getLeft(),prev))
			return false;
		if(root.getData()<prev)
			return false;
		prev=root.getData();
		
		return isBST(root.getRight(),prev);
	}

- Vir Pratap Uttam May 05, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 11 vote

/* check for BST */
	private static boolean isBST(BSTNode root) {
		if (root == null)
			return true;

		if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
			return false;
		if (root.getRight() != null
				&& findMin(root.getRight()) < root.getData())
			return false;

		if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
			return false;
		return true;
	}

- Vir Pratap Uttam May 05, 2015 | Flag Reply

Comment hidden because of low score. Click to expand.

of 5 vote

boolean isBST(TreeNode node,int min,int max)
	{
	
		if(node==null)
			return true;
		
		if(node.leftchild==null && node.rightchild==null)
			return true;
		
		else if(node.value>min&&node.value<max)
				return(isBST(node.leftchild, min, node.value)&&isBST(node.rightchild,node.value,max));
		else 
			return false;
		
	}

- RS October 26, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

This is a best solution, only 2 nodes are compared in each pass instead of all nodes in both subtrees.

- Anonymous October 27, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 1 vote

there is a minor bug the leftchild and rightchild being null doesnt make it BST because its own value needs to be checked so remove the 2nd if statement

- kkr.ashish November 06, 2013 | Flag

Comment hidden because of low score. Click to expand.

-3

of 3 votes

This will fail for the case:

- addsjunior December 15, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 2 vote

Somebody has already made excellent point "If the inorder traversal of the tree is sorted, the tree is BST else not."

Didn't get why people are still trying for other implementations?

- Kallu October 28, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

You are right, most implementations here will fail for the following case, returning that it is a BST:

- addsjunior December 15, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 1 vote

I guess the normal recursion, with two variable for allowed min and max would be sufficient for this question.
Following is the fully working code for the same.

#include <iostream>

#define INT_MAX 100000
#define INT_MIN -1

using namespace std;

class Node {
public:
    int val;
    Node * left;
    Node * right;
    Node() {val = -1; left = right = NULL; }
    Node(int x) {val = x; left = right = NULL; }
    ~Node() {
        delete left; delete right;
    }
};

bool isBST(Node * root, int max, int min) {
    if(root == NULL) {
       // cout << "null, returning true \n";
        return true;
    }
    cout << "At " << root ->val << endl;
    bool condition = (root -> left)? (root -> left -> val < root -> val) : true;
    condition = condition && ((root -> right) ? (root -> right -> val > root -> val): true);
    condition = condition && (root -> val < max && root -> val > min);
    if(condition == false) {
//        cout << "condition not met at " << root -> val << endl;
        return false;
    }
    return condition && 
        (isBST(root -> left, root -> val, min)) &&
        (isBST(root -> right, max, root -> val));
}

int main () {
    // Construction a Binary tree;
    Node * a = new Node(10);
    Node * b = new Node(5);
    Node * c = new Node(20);
    Node * d = new Node(1);
    Node * e = new Node(9);
    Node * f = new Node(15);
    Node * g = new Node(12);
    Node * h = new Node(17);
    Node * i = new Node(25);
    a -> left = b;
    a -> right = c;
    b -> left = d;
    b -> right = e;
    c -> left = f;
    f -> left = g;
    f -> right = h;
    c -> right = i;
    cout << isBST(a, INT_MAX, INT_MIN) << "\n";
    delete a;
    return 0;
}

- atuljangra66 October 29, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

Plus the complexity is O(num_of_nodes).

- atuljangra66 October 29, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 2 vote

If the inorder traversal of the tree is sorted, the tree is BST else not.

- Expressions October 27, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

@Swapnil/Urik - Will this fix my code

bool isValidBST(struct node *root) 
{ 
	static struct node *prev = NULL; 

	if(root==NULL) 
		return true; 

	return isValidBST(root->left); 

	if(prev && root->data<=prev->data) 
		return false; 
	prev = root; 

	return isValidBST(root->right); 
}

- Anon October 27, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

Sorry, below is the correct pheudo code, previous is a wrong post

boolean isBST (TreeNode node){
if(node == null) return true;
if (node.right == null && node.left == null) return true;
if(node.leftchild == null) {
if (node < node.right)
return isBST(node.rightchild);
else return false;
}

if(node.rightchild== null) {
if (node >node.left) return isBST(node.leftchild);
else return false;
}
return (isBST(node.rightchild) && isBST(node.leftchild));
}

- Anonymous October 27, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

boolean isBST (TreeNode node){
if(node == null) return true;
if(node.leftchild == null) return isBST(node.rightchild);
if(node.rightchild== null) return isBST(node.leftchild)
return (isBST(node.rightchild) && isBST(node.leftchild));
}

- Anonymous October 27, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

non-recursion implementation:

public static boolean isBST_iterative(BST node) {
		if(node == null)
			return true;
		
		List<BST> stack = new ArrayList<BST>();
		List<Integer> values = new ArrayList<Integer>();
		stack.add(node);
		values.add(Integer.MIN_VALUE);
		values.add(Integer.MAX_VALUE);

		while(stack.size() > 0) {
			BST bst = stack.remove(stack.size()-1);
			int high = values.remove(values.size()-1);
			int low = values.remove(values.size()-1);
			if(bst.value > high || bst.value < low)
				return false;
			
			// left child
			if(bst.left != null) {
				stack.add(bst.left);
				values.add(low);
				values.add(bst.value);
			}
			
			if(bst.right != null) {
				stack.add(bst.right);
				values.add(bst.value);
				values.add(high);
			}
		}
		
		return true;
	}

- Simon October 28, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

boolean isBST(TreeNode node) {
    if(node == null)
        return true;

    if(node.left == null || node.right == null) {
        if(node.left != null)
            return (node.value > node.left.value) && isBST(node.left);
        else if(node.right != null)
            return (node.value < node.right.value) && isBST(node.right);
        else
            return true;
    }
    return isBST(node.left) && isBST(node.right);
}

- frankliu November 05, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

boolean isBST(TNode root){
	return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
boolean isBST(TNode node, int lb, int rb) {
	if (!(lb < node.value < rb)){
		return false;
	}
	return isBST(node.left, lb, node.value) && isBST(node.right, node.value, rb);
}

- Loser November 07, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Just fix a small issue in my previous code.

boolean isBST(TreeNode node) {
    if(node == null)
        return true;

    if(node.left == null || node.right == null) {
        if(node.left != null)
            return (node.value > node.left.value) && isBST(node.left);
        else if(node.right != null)
            return (node.value < node.right.value) && isBST(node.right);
        else
            return true;
    }
    return (isBST(node.left) && node.value > node.left.value) && 
        (isBST(node.right) && node.value < node.right.value);
}

- shmilyaw November 09, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

#include <stdio.h>
#include <stdlib.h>

class Node
{
private:
int value;
Node *left,*right;
public:

Node(int nValue,Node * nLeft, Node *nRight)
{
this->value = nValue;
this->left = nLeft;
this->right = nRight;
}
Node * leftChild()
{
return left;
}
Node * rightChild()
{
return right;
}
int data() {return value;}
};

// If the root is root of BST returns the last node in the BST, else NULL
Node* isBST(Node * root,Node * predecessorNode)
{
if(!root)
{
return predecessorNode;
}

Node * predecessorOfRoot;
if(root->leftChild())
{
if((predecessorOfRoot = isBST(root->leftChild(),predecessorNode)) == NULL)
return NULL;
}
else
predecessorOfRoot = predecessorNode;

if(predecessorOfRoot && predecessorOfRoot->data() > root->data())
return NULL;

return isBST(root->rightChild(),root);

}

bool isBST(Node * root)
{
return root == NULL || isBST(root,NULL);
}

int main()
{
Node * root = new Node (8,
new Node(6,
new Node(4,NULL,NULL),
new Node(7,NULL,NULL)
),

new Node(12,
new Node(10,NULL,NULL),
new Node(14,NULL,NULL)
)
);

Node * root2 = new Node (8,
new Node(6,
new Node(12,NULL,NULL),
new Node(7,NULL,NULL)
),

new Node(12,
new Node(10,NULL,NULL),
new Node(14,NULL,NULL)
)
);

Node * root3 = new Node (8,
new Node(6,
new Node(4,NULL,NULL),
NULL
),

new Node(12,
new Node(10,NULL,NULL),
new Node(14,NULL,NULL)
)
);

puts((isBST(root)?"BST\n":"Not BST\n"));
puts((isBST(root2)?"BST\n":"Not BST\n"));
puts((isBST(root3)?"BST\n":"Not BST\n"));

}

- Anonymous December 11, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

#include <stdio.h>
#include <stdlib.h>

class Node 
{
    private:
    int value;
    Node *left,*right;
    public:
    
    Node(int nValue,Node * nLeft, Node *nRight)
    {
        this->value = nValue;
        this->left = nLeft;
        this->right = nRight;
    }
    Node * leftChild()
    {
        return left;
    }
    Node * rightChild()
    {
        return right;
    }
    int data() {return value;}
};

// If the root is root of BST returns the last node in the BST, else NULL
Node* isBST(Node * root,Node * predecessorNode)
{
    if(!root)
    {
        return predecessorNode;
    }
    
    Node * predecessorOfRoot;
    if(root->leftChild())
    {
        if((predecessorOfRoot = isBST(root->leftChild(),predecessorNode)) == NULL)
            return NULL;
    }
    else
        predecessorOfRoot = predecessorNode;
        
    if(predecessorOfRoot && predecessorOfRoot->data() > root->data())
      return NULL;
      
    return isBST(root->rightChild(),root); 

}

bool isBST(Node * root)
{
    return root == NULL || isBST(root,NULL);
}

int main()
{
    Node * root = new Node (8,
        new Node(6,
            new Node(4,NULL,NULL),
            new Node(7,NULL,NULL)
        ),
        
        new Node(12,
            new Node(10,NULL,NULL),
            new Node(14,NULL,NULL)
        )        
    );

    Node * root2 = new Node (8,
        new Node(6,
            new Node(12,NULL,NULL),
            new Node(7,NULL,NULL)
        ),
        
        new Node(12,
            new Node(10,NULL,NULL),
            new Node(14,NULL,NULL)
        )        
    );

    Node * root3 = new Node (8,
        new Node(6,
            new Node(4,NULL,NULL),
NULL
        ),
        
        new Node(12,
            new Node(10,NULL,NULL),
            new Node(14,NULL,NULL)
        )        
    );
    
    puts((isBST(root)?"BST\n":"Not BST\n"));
    puts((isBST(root2)?"BST\n":"Not BST\n"));
    puts((isBST(root3)?"BST\n":"Not BST\n"));


}

- Artaew December 11, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

python solution

def is_bst(node, _min=None, _max=None):
    if node == None:
        return True

    if (_min and node.value < _min) or (_max and node.value > _max):
        return False
        
    return is_bst(node.left, _min, node.value) and is_bst(node.right, node.value, _max)

- max December 15, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

public boolean isBST(Node node) {
	List<Integer> lst = new LinkedList<Integer>();
	getInOrder(node, lst);
	for (int i = 1; i < lst.size() - 1; i++) {
		if (lst.get(i) < lst.get(i - 1)) {
			return false;
		}
	}
	return true;
}
	
public void getInOrder(Node node, List<Integer> values) {
	if (node == null)
		return;

	getInOrder(node.left, values);
	values.add(node.value);
	getInOrder(node.right, values);
}

- addsjunior December 15, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

bool isBST(TreeNode * root, int min, int max, int &depth)
{
if (!root){
depth = 0;
return true;
}

if (root->val < min || root->val > max){
return false;
}

int ldep, rdep;
if (isBST(root->left, min, root->val, ldep) && isBST(root->right, root->val, max, rdep))
{
if ((ldep - rdep) <= 1 && (ldep - rdep) >= -1)
{
depth = 1+ max(ldep, rdep);
return true;
}
}

return false;
}

- BIN December 18, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

bool IsValidBST(TreeNode * root, TreeNode * & pre) {
  if (root == NULL) return true;
  if (!IsValidBST(root->left, pre)) return false;
  if (pre != NULL && pre->val >= root->val) return false;
  pre = root;
  if (!IsValidBST(root->right, pre)) return false;
  return true;
}

bool IsValidBST(TreeNode * root) {
  TreeNode * pre = NULL;
  return IsValidBST(root, pre);
}

- guoliqiang2006 December 29, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

-2

of 4 vote

bool isValidBST(struct node *root)
{
static struct node *prev = NULL;

if(root==NULL)
return true;

isValidBST(root->left);

if(prev && root->data<=prev->data)
return false;
prev = root;

isValidBST(root->right);
}

- Anon October 26, 2013 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

This seems right to me. Why was it down voted?

- tbag October 26, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 1 vote

Basically its not checking whether the values returned by

isValidBST(root->left); and isValidBST(root->right);

are true or false, and hence if in case it returns false, we are not able to find that out.

- Swapnil October 26, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

@Swapnil - I think this condition

if(prev && root->data<=prev->data) 
	return false;

will take care of that

- Anon October 26, 2013 | Flag

Comment hidden because of low score. Click to expand.

-2

of 2 votes

@Anon, Swapnil is right. You aren't propagating truth value up the tree.

bool isValidBST(struct node *root)
{
static struct node *prev = NULL;

if(root==NULL) return true;

if(!isValidBST(root->left) || (prev && root->data<=prev->data)) return false;

prev = root; 
return isValidBST(root->right);
}

@Swapnil, Check above please.

- Urik's twin Cookie Monster (dead now) October 27, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

@urik - Don't think your logic works. Where are you checking if isValidBST(root->right) returns true or false.

- Matt October 27, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

@Swapnil/Urik - Will this fix my code?

bool isValidBST(struct node *root) 
{ 
	static struct node *prev = NULL; 

	if(root==NULL) 
		return true; 

	return isValidBST(root->left); 

	if(prev && root->data<=prev->data) 
		return false; 
	prev = root; 

	return isValidBST(root->right); 
}

- Anon October 27, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 2 votes

@Matt, the last return statement funnels it upstream.

@Anon, your code will never go past the second return statement (the first naked out, meaning not surrounded by if statement).

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

I do not think it is a good idea to use static variable, if we have many cases to test,

- guoliqiang2006 December 29, 2013 | Flag

CareerCup

Facebook Interview Question for Software Engineer / Developers

Books

Videos

Resume Review

Mock Interviews