Binary search tree in C/C++

Question:

There is a problem. There is a binary tree. It is required to determine whether this tree is a binary search tree. It is desirable to present the solution in C++ or C. The time and space complexity of the algorithm, as well as the universality of the approach, are evaluated.

Answer:

UPD: I'm wrong, I'm correcting it.

Let's say 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. The space complexity is O(h), where h is the depth of the tree.

Scroll to Top