World's most popular travel blog for travel bloggers.

[Answers] Why isnt node checked for nil value in start when transplanting binary tree

, , No Comments
Problem Detail: 

Whilst I was reading CLRS I came across this:

When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u's parent becomes node v's parent, and u's parent ends up having v as its appropriate child.

TRANSPLANT(T, u, v) 1  if u.p == NIL 2      T.root = v 3  elseif u == u.p.left 4      u.p.left = v 5  else u.p.right =  v 6  if v != NIL 7      v.p = u.p 

Lines 1–2 handle the case in which u is the root of T . Otherwise, u is either a left child or a right child of its parent. Lines 3–4 take care of updating u.p.left if u is a left child, and line 5 updates u.p.right if u is a right child. We allow v to be NIL, and lines 6–7 update v.p if v is non-NIL.

Why wasn't v was checked for nil value in the starting of the procedure and if it was not checked then why was it checked in line 6. If v is nil then its parent will be its original parent and u's parent will reference to v - wouldn't this cause inconsistency in tree ?


Transplant is the sub-procedure used in deletion of a node from a binary search tree. It is used in binary search tree not in RB Trees or B-Trees.

Details about the book

Edition - 3rd

Print - 2nd

PageNo - 296

Asked By : Abhinav Garg

Answered By : Yuval Filmus

If $v$ is NIL then transplanting $v$ just transplants an empty tree. This is fine. It is handled in the exact same way as transplanting an actual tree, the only difference being that we don't need to update $v$'s parent pointer.

Could the code be structured differently? Probably. Why, then, did the authors choose this particular implementation? No deep reason. They programmed the algorithm, and that's the code they came up with. You might have come up with a different code. There's no one right answer in programming.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback