0

I have a slight confusion on inorder successor/predecessor if the BST is flipped. What I meant when the BST is flipped/reversed is that when all elements in the right subtree is smaller and all elements in the left subtree is greater. Normally the right subtree has greater value. What if it's the reversed, does the definition of inorder successor/predecessor still remains the same?

For normal tree, the inorder successor would be the leftmost child of the right subtree isn't it?

For flipped BST like the example below:

    8
    /\
   15 4
  /\  /\
20 10 6 2

Is the inorder successor of 8 is 10? Or is it 6 if we follow the "usual" definition of inorder successor?

Thanks!

1 Answer 1

0

If you do an in-order traversal of a reversed BST you will get the numbers sorted in descending order. So in that case the order for your values will be: 20, 15, 10, 8, 6, 4, 2. So the successor of 8 will be 6.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.