# BST Successor Proof

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?

• 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.
– D.W.
Commented Dec 2, 2013 at 4:22
• @D.W. I added my answer that I trued. Commented Dec 2, 2013 at 17:18

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?

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.

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