Skip to main content
Computer Science

Return to Answer

added 31 characters in body
Source Link
Russel
Russel
  • 2.8k
  • 1
  • 9
  • 16

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

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 case 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 when $x$'s subtree is part of $n$'s right subtree.

An additional case here 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$.

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

Source Link
Russel
Russel
  • 2.8k
  • 1
  • 9
  • 16

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 case 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 when $x$'s subtree is part of $n$'s right subtree.

An additional case here 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$.