# BST subtree value range

Suppose we have a node x in BST, and let max and min be the largest and smallest keys in the subtree rooted at x respectively. Prove that for any node n outside this subtree, the key of n is either greater than max or smaller than min. How should I approach this problem? I get that there are basiclly 3 cases for x,

1. x is the root of the entire tree, then this is trivial
2. x is the right child of its parent p, then p is smaller than min, also the left children of p is smaller than min
3. the reverse case of 2

I can basiclly recursively apply this, but how do I formally write a proof for it？

From how you state the conditions, it appears that $$x$$ and its subtree belongs to a larger tree and what you need is to prove that any other node $$n$$ in the larger tree but not in the subtree of $$x$$ must be smaller than $$min$$ (of $$x$$'s subtree) or larger than $$max$$, thus I do not see the need for case 1. I would also assume that keys of the nodes are distinct.
For your cases 2 and 3, instead of the parent you can generalize it so that $$n$$ is an ancestor of all nodes in $$x$$'s subtree. So if $$x$$ and its subtree is part of the left subtree of $$n$$ then key of $$n$$ is larger than $$max$$, since $$n$$ must be larger than all keys on its left subtree. You can have an analogous reasoning for $$min$$ when $$x$$'s subtree is part of $$n$$'s right subtree.
An additional case here (with two subcases) is if $$n$$ is not an ancestor and it belongs to a separate subtree. In this case, $$n$$ and $$x$$ will have the lowest common ancestor (lca), $$a$$. If $$x$$ is in the left subtree of $$a$$ and $$n$$ is in the right subtree then $$n \gt max$$ since $$max \lt a \lt n$$. Again, an analogous reasoning can be made when $$x$$ is in the right subtree while $$n$$ is in the left subtree of $$a$$.