0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.