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,
- x is the root of the entire tree, then this is trivial
- 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
- the reverse case of 2
I can basiclly recursively apply this, but how do I formally write a proof for it?