Binary Search tree help
Can somebody explain to me what this code is doing step by step?, thanks

TREE-SUCCESSOR(x)
      1 if right[x] ≠ NIL
      2 then return TREE-MINIMUM (right[x])
      3 y ← p[x]
      4 while y ≠ NIL and x = right[y]
      5 do x ← y
      6 y ← p[y]
      7 return y

Hi , the comments describe the code in a better way.
our job is to find the successor.

Binary Search tree help
Can somebody explain to me what this code is doing step by step?, thanks

TREE-SUCCESSOR(x)
      1 if right[x] ≠ NIL
      2 then return TREE-MINIMUM (right[x])  // if the node x has a right child , simply return that , that is the successor.
//now is the tricky part .. there is no node as the right child, 
traverse back along the parent path , which ever node along the path has a right childe is the successor
      3 y ← p[x]   // y <- parent of x 
      4 while y ≠ NIL and x = right[y] // as long as y is not nil and the current node is the right child , we keep going to the top, if it is the left child , we simply return the parent y.
      5 do x ← y // make the parent as the current node.
      6 y ← p[y]  // fetch the parent of the current node just set.
      7 return y // this will return either NIL , if we shoot past the root of the tree or we are not the right child of the parent , left child implies this node will be the successor.

Hope this helps! :)

Comments
Another useless bump of an ancient thread.
This article has been dead for over six months. Start a new discussion instead.