# Binary search tree in C / C ++

## Question:

There is a problem. There is a binary tree. It is required to determine if this tree is a binary search tree. It is desirable to present the solution in C ++ or C. The temporal and spatial complexity of the algorithm, as well as the versatility of the approach, are estimated.

UPD: mine is not true, correct.

Suppose the tree is defined like this:

``````struct BinaryTreeNode {
BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL),
parent(NULL), value(val) {}

BinaryTreeNode * leftChild;
BinaryTreeNode * rightChild;
BinaryTreeNode * parent;
int value;
};
``````

Then the verification algorithm will be as follows:

``````bool isBST(BinaryTreeNode * root)
{
return isBST_(root, 0, 0);
}

bool isBST_(BinaryTreeNode * node, BinaryTreeNode * minParent, BinaryTreeNode * maxParent)
{
if (minParent && minParent->value >= node->value)
return false;
if (maxParent && maxParent->value <= node->value)
return false;
if (node->leftChild != 0 && !isBST_(node->leftChild, minParent, node))
return false;
if (node->rightChild != 0 && !isBST_(node->rightChild, node, maxParent))
return false;
return true;
}
``````

The time complexity is O (n), where n is the number of nodes in the tree. Spatial complexity is O (h), where h is the depth of the tree.

Scroll to Top