Your code is generally correct. Just three notes.
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 incrementingindex
during execution ofInOrderArr (node.left, Array, index)
would not affect the position used bytreeArr[index] = node.key
. As a result only the rightmost path would be stored in the array.
To avoid that you'll have to ensure thatindex
is passed by reference, so that incrementation done by a callee advances the position used later by a caller.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?
Possibly it would be more efficient to drop the array and just recursively test a definition condition of BST?
Whenever we follow aleft
link we expect keys which are less than the current one. Whenever we follow theright
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);
}