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

Recommended Answers

All 3 Replies

have no idea because it isn't c or c++.

Looks like lua

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! :)

commented: Another useless bump of an ancient thread. -5
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.