retagged by
441 views
1 votes
1 votes

Given a binary search tree $T$, what is the path from $a$ node $x$ to its successor $y$, assuming that both $x$ and $y$ exist in $T$?

  1. if $x$ has a right child, then $y$ is the right child of $x$; otherwise, $y$ is the parent of $x$
  2. $y$ is the rightmost descendant of $x$
  3. if $x$ has a right child, then $y$ is the right child of $x$; otherwise, if $x$ is a left child, then $y$ is the parent of $x$; otherwise, $y$ is the left child
  4. if $x$ has a right child, then $y$ is the leftmost descendant of $x’s$ right child; otherwise, if $x$ is a left child, then $y$ is the parent of $x$; otherwise, $y$ is the parent of $x’s$ first ancestor $z$ such that $z$ is a left child
retagged by

2 Answers

0 votes
0 votes
All leftward descendants of x’s right child r have keys between x and r; finding the least of these gives the successor of x.

The other thing is that x might not have a right child.

In that case, x is the rightmost descendant of some ancestor z, which is the left child of a node y (or z is the root, in which case x has no successor in T ).

 Specifically, all rightward descendants of y’s left child z, including x, have keys between z and y. So y is the successor to x.

which supports option D .
Answer:

Related questions

1 votes
1 votes
1 answer
1
Bikram asked Jan 24, 2017
308 views
Suppose that six keys are inserted into an unbalanced binary search tree in the following order: $4, 6, 3, 8, 2$, and $5$.Then which of the following statements is/are co...
0 votes
0 votes
1 answer
3