Pseudo code to check if binary tree is a binary search tree - not sure about the recursion

Question

I have homeowork to write pseudo code to check if a valid binary tree is a search binary tree.

I created an array to hold the in-order values of the tree. if the in-order values are in decreasing order it means it is indeed BST. However I've got some problem with the recursion in the method InOverArr.

I need to update the index of the array in order to submit the values to the array in the order they are at the tree.

I'm not sure the index is really updated properly during the recursion.. is it or not? and if you see some problem can you help me fix this? thanks a lot

pseudo code

first function

IsBST(node)

size ← TreeSize(node)

create new array TreeArr of Size number of cells

index ← 0

few comments: now we use the IN_ORDER procedure with a small variation , I called the new version of the procedure: InOrderArr the pseudo code of InOrderArr is described below IsBST

InOrderArr(node, TreeArr, index)

for i from 1 to size-1 do

if not (TreeArr[i] > TreeArr[i-1]) return false

return true

second function

InOrderArr (node, Array, index) if node = NULL then return

else

InOrderArr (node.left, Array, index)

treeArr[index] = node.key

index ← index + 1

InOrderArr (node.right, Array, index)

Return

Answer 1

Your code is generally correct. Just three notes.

1. The correctness of the code depends on the implementation, specifically on the way of index handling. Many programming languages pass arguments to subroutines by value. That means the subroutine receives a copy of the value and modifications made to the parameter have no effect on the original value. So incrementing index during execution of InOrderArr (node.left, Array, index) would not affect the position used by treeArr[index] = node.key. As a result only the rightmost path would be stored in the array.
   To avoid that you'll have to ensure that index is passed by reference, so that incrementation done by a callee advances the position used later by a caller.

2. BST is usually defined so that the left subtreee of a node contains keys that are less than that node's key, and the right subtree contains nodes with greater keys – see Wikipedia's article on BST. Then the inorder traversal retrieves keys in ascending order. Why do you expect descending order?

3. Possibly it would be more efficient to drop the array and just recursively test a definition condition of BST?
   Whenever we follow a left link we expect keys which are less than the current one. Whenever we follow the right link we expect keys greater the the current one. So for most subtrees there is some interval of keys values, defined by some ancestor nodes' keys. Just track those keys and test whether the key falls inside the current valid interval. Be sure to handle 'no left end defined' condition on the letfmost path and 'no right end' on the rightmost path of the tree. At the root node there's no ancestor yet, so the root key is not tested at all (any value is OK).

EDIT

C code draft:

    // Test a node against its closest left-side and right-side ancestors
    boolean isNodeBST(NODE *lt, NODE *node, NODE *rt)
    {
        if(node == NULL)
            return true;
        if(lt != NULL && node->key < lt->key)
            return false;
        if(rt != NULL && node->key > rt->key)
            return false;

        return
            isNodeBST(lt, node->left, node) &&
            isNodeBST(node, node->right, rt);
    }

    boolean isTreeBST(TREE *tree)
    {
       return isNodeBST( NULL, tree->root, NULL);
    }