c++ my binary tree is well formed

Question

i propose a recursive implementation for checking whether binary search tree is valid:

/*
  Return true if binary tree is a binary search tree
*/
bool BinaryTree::isBinarySearchTree(BinaryTree* tree, int& prev)
{
    if(!isBinarySearchTree(tree->left, tree->data)) // left
         return false;

    if(tree->value > prev) // here
        return false;
    else
        prev = tree->value;

    return isBinaryTree(tree->right); // right
}

i have big doubt on the second check,

    if(tree->value > prev) // here
        return false;

whats your favorite c++ implementation for this problem?

EDIT

how would you extend to find larger BST in given tree?

Answer 1

It's amazing how many people get this wrong.

Here's an example of a tree which the naive solution fails to reject:

                5
              /   \
             /     \
            4       6
           / \     / \
          1   7   1   7

Every invocation of a naive check will succeed, since every parent is between its children. Yet, it is clearly not a well-formed binary search tree.

Here's a quick solution:

bool test(Tree* n,
  int min=std::numeric_limits<int>::min(),
  int max=std::numeric_limits<int>::max()) {
  return !n || ( 
         min < n->data && n->data < max
         && test(n->left, min, n->data)
         && test(n->right, n->data, max));
}

This isn't perfect, because it requires that neither INT_MIN nor INT_MAX be present in the tree. Often, BST nodes are ordered by <= instead of <, and making that change would only reserve one value instead of two. Fixing the whole thing is left as an exercise.

Here's a demonstration of how the naive test gets it wrong:

#include <iostream>
#include <limits>
#define T new_tree

struct Tree{
  Tree* left;
  int data;
  Tree* right;
};

Tree* T(int v) { return new Tree{0, v, 0}; }
Tree* T(Tree* l, int v, Tree* r) { return new Tree{l, v, r}; }

bool naive_test(Tree* n) {
  return n == 0 || ((n->left == 0 || n->data > n->left->data)
      && (n->right == 0 || n->data < n->right->data)
      && naive_test(n->left) && naive_test(n->right));
}

bool test(Tree* n,
  int min=std::numeric_limits<int>::min(),
  int max=std::numeric_limits<int>::max()) {
  return !n || ( 
         min < n->data && n->data < max
         && test(n->left, min, n->data)
         && test(n->right, n->data, max));
}

const char* goodbad(bool b) { return b ? "good" : "bad"; }

int main(int argc, char**argv) {
  auto t = T( T( T(1),4,T(7)), 5, T(T(1),6,T(7)));
  std::cerr << "Naive test says " << goodbad(naive_test(t))
            << "; Test says " << goodbad(test(t)) << std::endl;
  return 0;
}

Answer 2

Recursive impelentation:

bool is_bst (node *root, int min = INT_MIN, int max = INT_MAX)
{
    if (root)
    {
        // check min/max constaint
        if (root->data <= min || root->data >= max) 
          return false;

        if (root->left != NULL)
         {
           // check if the left node is bigger
           // or if it is not BST tree itself
           if (root->data < root->left->data ||
               !is_bst (root->left, min, root->data))
            return false;
         }

        if (root->right != NULL)
         {
           // check if the right node is smaller
           // or if it is not BST tree itself
           if (root->data > root->right->data ||
               !is_bst (root->right, root->data, max))
            return false;
         }
    }
    return true;
}

Iterative impelentation

    node_type curr = root;
    node_type prev = null;
    std::stack<node_type> stack;
    while (1)
    {
        if(curr != null)
        {
            stack.push (curr);
            curr = curr->left;
            continue;
        }
        if(stack.empty()) // done
            return true;

        curr = stack.pop ();
        if (prev != null)
        {   
            if(curr->data < prev->data)
                return false;
        }
        prev = curr;
        curr = curr->right;
    }