I'm struggling with following problem:

Write function which for given binary tree returns a root of minimal height which is not BST or NIL when tree is BST.

I know how to check if tree is BST but don't know how to rewrite it. I would be grateful for an algorithm in pseudo code.

# Best How To :

Rather than jumping right into an algorithm that works here, I'd like to give a series of observations that ultimately leads up to a really nice algorithm for this problem.

First, suppose that, for each node in the tree, you knew the value of the largest and smallest values in the subtree rooted at that node. (Let's denote these as min(x) and max(x), where x is a node in the tree). Given this information, we can make the following observation:

**Observation 1:** A node x is the root of a non-BST if x ≤ max(x.left) or if x ≥ min(y.right)

This is not an if-and-only-if condition - it's just an "if" - but it's a useful observation to have. The reason this works is that if x ≤ max(x.left), then there is a node in x's left subtree that's not smaller than x, meaning that the tree rooted at x isn't a BST, and if x > min(x.right), then there's a node in x's right subtree that's not larger than x, meaning that the tree rooted at x isn't a BST.

Now, it's not necessarily the case that any node where x < min(x.right) and x > max(x.left) is the root of a BST. Consider this tree, for example:

```
4
/ \
1 6
/ \
2 5
```

Here, the root node is larger than everything in its left subtree and smaller than everything in its right subtree, but the entire tree is itself not a BST. The reason for this is that the trees rooted at 1 and 6 aren't BSTs. This leads to a useful observation:

**Observation 2:** If x > max(x.left) and x < min(x.right), then x is a BST if and only if x.left and x.right are BSTs.

A quick sketch of a proof of this result: if x.left and x.right are BSTs, then doing an inorder traversal of the tree will list off all the values in x.left in ascending order, then x, then all the values in x.right in ascending order. Since x > max(x.left) and x < min(x.right), these values are sorted, so the tree is a BST. On the other hand, if either x.left or x.right are not BSTs, then the order in which these values come back won't be sorted, so the tree isn't a BST.

These two properties give a really nice way to find every node in the tree that isn't the root of a BST. The idea is to work through the nodes in the tree from the leaves upward, checking whether each node's value is greater than the max of its left subtree and less than the min of its right subtree, then checking whether its left and right subtrees are BSTs. You can do this with a postorder traversal, as shown here:

```
/* Does a postorder traversal of the tree, tagging each node with its
* subtree min, subtree max, and whether the node is the root of a
* BST.
*/
function findNonBSTs(r) {
/* Edge case for an empty tree. */
if (r is null) return;
/* Process children - this is a postorder traversal. This also
* tags each child with information about its min and max values
* and whether it's a BST.
*/
findNonBSTs(r.left);
findNonBSTs(r.right);
/* If either subtree isn't a BST, we're done. */
if ((r.left != null && !r.left.isBST) ||
(r.right != null && !r.right.isBST)) {
r.isBST = false;
return;
}
/* Otherwise, both children are BSTs. Check against the min and
* max values of those subtrees to make sure we're in range.
*/
if ((r.left != null && r.left.max >= r.value) ||
(r.right != null && r.right.min <= r.value)) {
r.isBST = false;
return;
}
/* Otherwise, we're a BST, and our min and max value can be
* computed from the left and right children.
*/
r.isBST = true;
r.min = (r.left != null? r.left.min : r.value);
r.max = (r.right != null? r.right.max : r.value);
}
```

One you've run this pass over the tree, every node will be tagged with whether it's a binary search tree or not. From there, all you have to do is make one more pass over the tree to find the deepest node that's not a BST. I'll leave that as a proverbial exercise for the reader. :-)

Hope this helps!