CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
eleven
eleven

Reputation: 369

How to calculate parent based on successor in Binary Search Tree (BST)

As the title implies, if we have node x in a Binary Search Tree (BST) and we know the info of x.successor instead of x.parent, also we know x.left and x.right. How to calculate x.parent based on the above information.

I decide to analyze it on two cases: (root have height 0)

  1. if x does not have right child, x.successor's height must less than x. In other words, x.successor is in the "upper level" of x.
  2. if x have right child, x.successor's height must greater than x. It means x.successor is in the "lower level" of x.

For the first case, we could have the following pseudo-code.

y = x.succ
if x.right == NIL
     z = y.left
     while x != z
         y = z;
         z = z.right
return z

How to handle the second case? what happened if x.right != NIL ?

                        15

             6                       18
         3       7              17        19
       2   4       13                         20
                 9

How to retrieve the parent of node 18 and 19, since there rightmost node 20 does not have successor, so it will return NIL.

Upvotes: 1

Views: 381

Answers (1)

lucian
lucian

Reputation: 527

we can not get the parent always based on your info. for instance, 2 nodes, nodeOne.right = x we only know x left = null, right = null, successor = null we are not able to retrieve nodeOne

we can get the parent when x is not at the right-most branch(which means it has some ancestor whose left branch includes the x).

the algorithm could be:

continue find the right son, right grandson, ..., till there is none then get the successor, and go into your code(your code is a little bit err?)

function getParent(Node node){
   Node right = node;
   for(;right.right != null; right = right.right){
   }
   Node successor = right.successor;
   if (successor == null)
     return null;

   if (successor.left == node)
     return successor;

   for(Node p = successor.left; p!= null; p=p.right){ 
     if (p.right == node){
       return p;
     }
   }
   return null;  
}

Upvotes: 1

Related Questions