CareerCup

the question asks for a Valid Binary Tree, not a valid Binary Search Tree, so, the min max should not be a concern, rather whether the tree has two children per node at most.

The question is "checking the tree is Binary Tree"
However the code is Binary Search Tree...
So I think the question might be typing error????

Binary tree will have atmost 2^h-1 nodes (full binary tree). Count the number of nodes and see if n <= 2h^-1 (n=number of nodes, h=height of the tree). If its satisfies this condition then the tree is said to be binary tree.

public boolean isBinaryTree(Node root) {
if (root == null) return true;
else if (root.children.length > 2) return false;
return isBinaryTree(root.children[0]) && isBinaryTree(root.children[1]);
}

public class BST {	
	
	private static Node prevNode = null;
	
	public boolean isBST(Node root){
		if (root != null){
			if (!isBST(root.left)){
				return false; 
			}
			if (prevNode != null && prevNode.data >= root.data){
				return false;
			}
			prevNode = root;
			return isBST(root.right);
		}
		return true;
	}

fdsafdsa

static boolean checkBST(Node root, int minValue, int maxValue)
{
if(root == null)
return true;
else if( root.data > minValue && root.data < maxValue && checkBST(root.left,minValue,root.data)
&& checkBST(root.right,root.data,maxValue))
return true;
else
return false;
}

static boolean checkBST(Node root) {
if(root == null)
return true;
/* 2nd approach : O(n2)
* else if(isLeftSubtreeLesser(root.left,root.data) && isRightSubtreeGreater(root.right,root.data) && checkBST(root.left) && checkBST(root.right))
return true;*/
// 1st Approach : O(n)
else if(checkBST(root,Integer.MIN_VALUE, Integer.MAX_VALUE))
return true;
else
return false;
}

static boolean checkBST(Node root, int minValue, int maxValue)
	{
		if(root == null)
			return true;
		else if( root.data > minValue && root.data < maxValue && checkBST(root.left,minValue,root.data) 
				&& checkBST(root.right,root.data,maxValue))
			return true;
		else
			return false;
	}

	static boolean checkBST(Node root) {
	    if(root == null)
	        return true;
	    /* 2nd approach : O(n2)
	     * else if(isLeftSubtreeLesser(root.left,root.data) && isRightSubtreeGreater(root.right,root.data) && checkBST(root.left) && checkBST(root.right))
	                return true;*/
	    // 1st Approach : O(n)
	    else if(checkBST(root,Integer.MIN_VALUE, Integer.MAX_VALUE))
	    	return true;
	    else 
	        return false;     
	    }

you could iterate the tree in an in-order fashion, you need to check if your values are ordered :)

/**
* Binary Search Tree ,value of left child must be less than value of parent, value of right child must be greater
* than value of parent
* Then we can use inorder traversal, if BST , after in order, all value of node must be sorted
* if previous value is greater current value is invalid
*/
public boolean isValidBSTCaller(TreeNode root) {
int prev = Integer.MIN_VALUE;
return isValidBST(root, prev);
}

public boolean isValidBST(TreeNode root, int prev) {
if (root==null) return true;
return (isValidBST(root.left,prev)) && (root.data>= prev) && isValidBST(root.right,prev=root.data);
}

public boolean isValidBSTCaller(TreeNode root) {
int prev = Integer.MIN_VALUE;
return isValidBST(root, prev);
}
// BST, left key <= parent key, right key >= parent key, inorder list sorted key data
// once prev key > current key, invalid
public boolean isValidBST(TreeNode root, int prev) {
if (root==null) return true;
return (isValidBST(root.left,prev)) && (root.data>= prev) && isValidBST(root.right,prev=root.data);
}

struct node* check(struct node* root)
{
	struct node* true=NULL;
	struct node* false;
	int key=root->data;
	if(root==NULL)
     return true;
     if(key > root->right->data || key <= root->left->data)
        return false;
    if(key<root->right)
	return check(root->right);
	if(key>root->left)
	return check(root->feft); 
	}
	
	boolean getBinary()
 	{
		struct node* a;
		a=check(head);
		if(a)
		return true;
		else 
		return false;
	}

struct node* check(struct node* root)
{
	struct node* true=NULL;
	struct node* false;
	int key=root->data;
	if(root==NULL)
     return true;
     if(key > root->right->data || key <= root->left->data)
        return false;
    if(key<root->right)
	return check(root->right);
	if(key>root->left)
	return check(root->feft); 
	}
	
	boolean getBinary()
 	{
		struct node* a;
		a=check(head);
		if(a)
		return true;
		else 
		return false;
	}

Using min-max approach:

public static boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}
	
	// int min, int max version
	public static boolean isValidBST(TreeNode root, long min, long max) {
		if (root == null) {
			return true;
		}
		if (root.val <= min || root.val >= max) {
			return false;
		}
		return isValidBST(root.left, min, root.val) && 
				isValidBST(root.right, root.val, max);
	}

struct node* check(struct node* root)
{
	struct node* true=NULL;
	struct node* false;
	int key=root->data;
	if(root==NULL)
     return true;
     if(key > root->right->data || key <= root->left->data)
        return false;
    if(key<root->right)
	return check(root->right);
	if(key>root->left)
	return check(root->feft); 
	}
	
	boolean getBinary()
 	{
		struct node* a;
		a=check(head);
		if(a)
		return true;
		else 
		return false;
	}