How to prove a binary tree is indeed a binary search tree?

Question

Hello,

Given a simple binary tree, how can we prove that tree is a binary search tree? When we traverse a binary tree, how do we know if the node we are on is the left or right child of its parent? I came up with one solution where i would pass some flag in recursive function call which could keep track of whether the node is left or right child of its parent as well as we need one parent node pointer through which we can compare :-

if(flag == 'L' && node->value < node->parent->value)
   then continue recursion;
else{
   print "not a binary search tree"
   exit;
}

In the same way one if condition is needed for R. Apart from this can you think any other efficient way?

Thanks in advance :)

Answer 1

I would just check:

currentNode.Left.max() < currentNode.Value and currentNode.Left.isBinarySearchTree(). If both are fulfilled, it's a binary search tree.

Edit:

The above does traverse the left tree twice (once for the max() and once for isBinarySearchTree. However, it can be done using just one traversal:

Store the minimum and maximum element in your tree class. Updates, etc. of course can be done in O(1) space and time.

Then, instead of using max(), make a method isInRange(m,M), that checks, whether a (sub)tree contains only elements in the range (m,m+1,...,M).

Define isInRange(m,M) as follows:

bool isInRange(m,M){
 if (m < currentNode.Value <= M){
  return (currentNode.Left.isInRange(m, currentNode.Value) && currentNode.Right.isInrange(currentNode.Value+1, M));
 }
 return false;
}

Then, the initial call would be root.isInRange(globalmin, globalmax).

Didn't test it so I don't know if it matters in performance.

Answer 2

Do you already have a way to iterate/traverse over the elements of the tree? Then you can simply traverse the tree and check that each element is greater than the previous one

Answer 3

The simple answer is to do an in-order depth-first tree traversal and check that the nodes are in order.

Example code (Common Lisp):

(defun binary-search-tree-p (node)
  (let ((last-value nil))
    (labels ((check (value)
               (if (or (null last-value)        ; first checked value
                       (>= value last-value))
                   (setf last-value value)
                   nil))
             (traverse (node)
               (if (null node)
                   t
                   (and (traverse (left node))        ; \
                        (check (value node))          ;  > in-order traversal
                        (traverse (right node))))))   ; /
      (traverse node))))

Answer 4

You can do a depth-first search over the tree without needing to cache the minimum and maximum values for each subtree in a single pass, but you have to be careful, as comparing the values between and parent and its children is not enough. For example, in the tree:

(10
   (7
     nil
     (20 nil nil)
   )
   nil
)

The left child (7) of the root (10) satisfy the inequalty (7 <= 10), as does the right child (20) of 7 (20 >= 7). However, the tree is not a BST (Binary Search Tree), because 20 should not be in the left subtree of 10.

To fix this, you may do a traversal passing to extra arguments specifying the valid interval for the subtree.

// The valid interval for the subtree root's value is (lower_bound, upper_bound).
bool IsBST(const node_t* tree, int lower_bound, int upper_bound) {
  if (tree == NULL) return true;  // An empty subtree is OK.
  if (tree->value <= lower_bound) return false;  // Value in the root is too low.
  if (tree->value >= upper_bound) return false;  // Value in the root is too high.

  // Values at the left subtree should be strictly lower than tree->value
  // and be inside the root valid interval.
  if (!IsBST(tree->left, lower_bound, tree->value))
    return false;

  // Values at the left subtree should be strictly greater than tree->value
  // and be inside the root valid interval.
  if (!IsBST(tree->right, tree->value, upper_bound))
    return false;

  // Everything is OK, it is a valid BST.
  return true;  
}

Notice that by keeping the original valid interval, the function will detect that 20 is invalid at that position, as it is not inside (7, 10). The first call should be done with an infinite interval, like:

IsBST(tree, INT_MIN, INT_MAX);

Hope this helps.