Yet another algorithm for checking BST tree property

#1

Hello, I come up with an algorithm with O(n) time complexity and O(logn) space complexity to solve the problem 15.1 of checking the BST property of a n-node binary tree. The algorithm directly uses the BST definition: root.data >= max_of_left_subtree and root.data <= min_of_right_subtree. It has O(n) complexity by computing the min and max of subtrees in a bottom-up manner. The call stack has O(logn) complexity.
I just want to write down here as an addition to the algorithms in the book and maybe you may find any bug or incorrectness.

template <typename T>
bool IsBinaryTreeBST(const unique_ptr<BinaryTreeNode<T>>& root, T& min, T& max) {
        if (!root) return true;

        T min_l = 0, max_l = 0, min_r = 0, max_r = 0;
        if (root->left && !IsBinaryTreeBST(root->left, min_l, max_l) ||
            root->right && !IsBinaryTreeBST(root->right, min_r, max_r))
                return false;

        min = root->left ? max_l : root->data;
        max = root->right ? min_r : root->data;

        return (root->data >= min && root->data <= max);
}

template <typename T>
bool IsBinaryTreeBST(const unique_ptr<BinaryTreeNode<T>>& root) {
        T min, max;
        return IsBinaryTreeBST(root, min, max);
}
0 Likes
#2

Hey Duc,

It definitely looks like an interesting idea because it looks similar to the one on the book but definitely has some difference. I can somehow understand the reason why you say this is “bottom up” because you are not passing min and max initially but retrieve the from the subtree function calls.

I personally think this algorithm is correct, and thanks for providing this alternative idea on this problem!

0 Likes