CareerCup

Do inorder traversal and compare if the successor is no less than the predecessor. O(n).

int check_binarytree(tree *t)
{
if(!t)
return true;
if(t->left&&(maxvalue(t->left)>t->element))
return  false;
if(t->right&&(minvalue(t->right)<=t->element))
return  false;
if(!check_binarytree(t->left)||!check_binarytree(t->right))
return false;
return true;
}

comments on this are welcome

Since we don't know that it's a binary tree, it's presumed that its children nodes are stored in some enumerable structure. As long as no more than 2 children are non-null, and that the first non-null child has value less than and second non-null child has value greater than, then it's a binary tree.

public bool isBinaryTree(Node n, bool isLeftChild, Node Parent)
{
   int count=0;
   int[] childIndexes = new int{-1,-1};

   for (int s=0; s < n.Children.Count; s++)
   {
       if ( n.Children[0] != null )
       {   
           if (count==2) return false;
           childIndexes[count++] = s;
       }
   }

   if (parent != null && isLeftChild)
   {
       if (n.Value > parent.Value)
           return false;

 
   }
   else if (parent != null && !isLeftChild)
   {
        if (n.Value < Parent.Value) return false;
   }
   bool isLeft = true;
   for (int r=0; r< count; r++)
    {
        if (! isBinaryTree(n.Children[childIndexes[r]], isLeft, n) ) return false;
        isLeft = false;
    }
    return true;
}

public class Node{
int data;
Node[] children ;
}

public void isBST(Node root){
if(root == null){
return true;
}
int numChild = 0;
Node left = null;
Node right = null;
for(int i =0;i<root.children.size();i++){
if(root.children[i] != null){
numChild++;
if(left == null){
left = root.children[i];
}else{
right = root.children[i];
}
}
}
if(numChild > 2){
return false;
}
boolean leftOk = false;
boolean rightOk = false;
if(left == null || (left.data <= root.data && isBST(left))){
leftOk = true;
}
if(right == null || (right.data > root.data && isBST(right)){
rightOk = true;
}
return leftOk && rightOk ;
}

public class Node{
int data;
Node[] children ;
}

public void isBST(Node root){
if(root == null){
return true;
}
int numChild = 0;
Node left = null;
Node right = null;
for(int i =0;i<root.children.size();i++){
if(root.children[i] != null){
numChild++;
if(left == null){
left = root.children[i];
}else{
right = root.children[i];
}
} 
}
if(numChild > 2){
return false;
}
boolean leftOk = false;
boolean rightOk = false;
if(left == null || (left.data <= root.data && isBST(left))){
leftOk = true;
}
if(right == null || (right.data > root.data && isBST(right)){
rightOk = true;
}	
return leftOk && rightOk ;
}

You should also make sure that each node has no more than two children