key stored at its rootthe minimum key of the left subtreeand the minimum key of the right subtree the maximum key is computed similarly note that the minimum can be in either subtreesince general binary tree may not satisfy the bst property the problem with this approach is that it will repeatedly traverse subtrees in the worst-casewhen the tree is bst and each node' left child is emptythe complexity is ( )where is the number of nodes the complexity can be improved to (nby caching the largest and smallest keys at each nodethis requires (nadditional storage for the cache we now present two approaches which have (ntime complexity the first approach is to check constraints on the values for each subtree the initial constraint comes from the root every node in its left (rightsubtree must have key less than or equal (greater than or equalto the key at the root this idea generalizesif all nodes in tree must have keys in the range [lu]and the key at the root is (which itself must be between [lu]otherwise the requirement is violated at the root itself)then all keys in the left subtree must be in the range [lw]and all keys stored in the right subtree must be in the range [wuas concrete examplewhen applied to the bst in figure on page the initial range is [-for the recursive call on the subtree rooted at bthe constraint is [- ]the is the upper bound required by on its left subtree for the recursive call starting at the subtree rooted at fthe constraint is [ for the recursive call starting at the subtree rooted at kthe constraint is [ the binary tree in figure on page is identified as not being bst when the recursive call reaches --the constraint is [- ]but the key at is so the tree cannot satisfy the bst property def is_binary_tree_bst (tree low_range =float('-inf ')high_range float('inf '))if not treereturn true elif not low_range <tree data <high_range return false return is_binary_tree_bst (tree left low_range tree dataand is_binary_tree_bst (tree right tree data high_range )the time complexity is ( )and the additional space complexity is ( )where is the height of the tree alternativelywe can use the fact that an inorder traversal visits keys in sorted order furthermoreif an inorder traversal of binary tree visits keys in sorted orderthen that binary tree must be bst (this follows directly from the definition of bst and the definition of an inorder walk thus we can check the bst property by performing an inorder traversalrecording the key stored at the last visited node each time new node is visitedits key is compared with the key of the previously visited node if at any step in the walkthe key at the previously visited node is greater than the node currently being visitedwe have violation of the bst property all these approaches explore the left subtree first thereforeeven if the bst property does not hold at node which is close to the root ( the key stored at the right child is less than the key stored at the root)their time complexity is still (nwe can search for violations of the bst property in bfs mannerthereby reducing the time complexity when the property is violated at node whose depth is small specificallywe use queuewhere each queue entry contains nodeas well as an upper and lower bound on the keys stored at the subtree rooted at that node the queue is initialized to the