-1
$\begingroup$

I'm studying for my CS final and I can't seem to get the anywhere with one of the questions.

This is the question:

Prove that if a node in a BST has a successor, but has no right child, then its successor must be an ancestor. (We will consider only BSTs with distinct elements.)

I know that a successor is the node that replaces the deleted node, and that we only need to worry about this case when the node being deleted has two children, but I can't seem to start this proof.

Any help?

$\endgroup$
2
  • $\begingroup$ What have you tried, to prove it yourself? Have you tried working it out by hand on a few small examples, to see if you can spot a pattern? Also, to help make this question more findable by search, I suggest spelling out what the BST acronym stands for. $\endgroup$
    – D.W.
    Commented Dec 2, 2013 at 4:22
  • $\begingroup$ @D.W. I added my answer that I trued. $\endgroup$ Commented Dec 2, 2013 at 17:18

2 Answers 2

1
$\begingroup$

This might depend delicately on how you define a successor. From what I understand of this and from your post, a successor to a node N is the node that replaces N when N is deleted (preserving the properties of BST). This definition doesn't necessarily mean that each node has a unique successor. Consider the following example:

10
  \
   14
  /
13

What is the successor to the node 14? It can just as easily be either 10 or 13.

I think this might be a counter-example to your question's claim. Delete node 14 and a BST tree that results is

10
  \
   13

14 had no right child and its successor is not its ancestor.

Am I not understanding something?

$\endgroup$
0
-1
$\begingroup$

This is my attempt - I'm not sure if it's correct or not.

Start proof:

  • A successor is the node that replaces a node when it is deleted, while preserving the properties of the BST.
  • The tree is traversed in post order (Left, Right, Node).

Consider the tree:

    A
     \
      B
     /
    C

The order in which the nodes are visited to delete node B is as follows:

C, B

C has already been visited. B’s successor must be A.

End proof.

$\endgroup$
1
  • $\begingroup$ To whomever marked me down, can you help me understand why I'm wrong? $\endgroup$ Commented Dec 2, 2013 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.